Efficient enumeration of optimal and approximate solutions of a scheduling problem

Sergey Sevastyanov; Bertrand M.T. Lin

Efficient enumeration of optimal and approximate solutions of a scheduling problem

Department of Information Management and Finance

Research output: Contribution to conference › Paper › peer-review

Abstract

When dealing with optimization problems, one normally searches for a "best solution" with respect to a certain objective function. But in reality, the decisionmaking process is not that simple, and while solving a real life problem, we choose a "proper" solution from among those ones that are good enough with respect to a given criterion, while our ultimate choice depends on a variety of difficult-toformalize conditions. In that case we may be interested in enumerating (without repetition) the set of all approximate solutions that meet a given bound on inaccuracy.

Original language	English
Pages	248-251
Number of pages	4
State	Published - 14 Jun 2011
Event	10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - Frascati, Italy Duration: 14 Jun 2011 → 16 Jun 2011

Conference

Conference	10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011
Country/Territory	Italy
City	Frascati
Period	14/06/11 → 16/06/11

Keywords

Flowshop scheduling
Listing algorithm
Makespan
Permutational schedule
Polynomial delay
Polynomial space

Cite this

@conference{7aaa43418c4242fd90cc622aabe8a4b2,

title = "Efficient enumeration of optimal and approximate solutions of a scheduling problem",

abstract = "When dealing with optimization problems, one normally searches for a {"}best solution{"} with respect to a certain objective function. But in reality, the decisionmaking process is not that simple, and while solving a real life problem, we choose a {"}proper{"} solution from among those ones that are good enough with respect to a given criterion, while our ultimate choice depends on a variety of difficult-toformalize conditions. In that case we may be interested in enumerating (without repetition) the set of all approximate solutions that meet a given bound on inaccuracy.",

keywords = "Flowshop scheduling, Listing algorithm, Makespan, Permutational schedule, Polynomial delay, Polynomial space",

author = "Sergey Sevastyanov and Lin, {Bertrand M.T.}",

year = "2011",

month = jun,

day = "14",

language = "English",

pages = "248--251",

note = "10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 ; Conference date: 14-06-2011 Through 16-06-2011",

}

TY - CONF

T1 - Efficient enumeration of optimal and approximate solutions of a scheduling problem

AU - Sevastyanov, Sergey

AU - Lin, Bertrand M.T.

PY - 2011/6/14

Y1 - 2011/6/14

N2 - When dealing with optimization problems, one normally searches for a "best solution" with respect to a certain objective function. But in reality, the decisionmaking process is not that simple, and while solving a real life problem, we choose a "proper" solution from among those ones that are good enough with respect to a given criterion, while our ultimate choice depends on a variety of difficult-toformalize conditions. In that case we may be interested in enumerating (without repetition) the set of all approximate solutions that meet a given bound on inaccuracy.

AB - When dealing with optimization problems, one normally searches for a "best solution" with respect to a certain objective function. But in reality, the decisionmaking process is not that simple, and while solving a real life problem, we choose a "proper" solution from among those ones that are good enough with respect to a given criterion, while our ultimate choice depends on a variety of difficult-toformalize conditions. In that case we may be interested in enumerating (without repetition) the set of all approximate solutions that meet a given bound on inaccuracy.

KW - Flowshop scheduling

KW - Listing algorithm

KW - Makespan

KW - Permutational schedule

KW - Polynomial delay

KW - Polynomial space

UR - http://www.scopus.com/inward/record.url?scp=84883127154&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84883127154

SP - 248

EP - 251

T2 - 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011

Y2 - 14 June 2011 through 16 June 2011

ER -

Efficient enumeration of optimal and approximate solutions of a scheduling problem

Abstract

Conference

Keywords

Other files and links

Fingerprint

Cite this