Volume 41, Number 1, January-March 2007
|Page(s)||1 - 18|
|Published online||15 June 2007|
Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
LAMSADE – Université Paris Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France; email@example.com
2 Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus; firstname.lastname@example.org
3 MACSI team of INRIA-Lorraine and LORIA-INPL, École des Mines de Nancy, Parc de Saurupt, 54042 Nancy Cedex, France; email@example.com
Accepted: 15 June 2006
We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.
Key words: Scheduling / single machine / schedule flexibility / maximization problems / active and non-delay schedules.
© EDP Sciences, ROADEF, SMAI, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.