HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Worst case performance evaluation of flexible solutions in single machine scheduling

Mohamed Ali Aloulou 1 Marie-Claude Portmann 1 Mikhail Y. Kovalyov 2
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we consider the problem of evaluating the worst case performance of flexible solutions in single machine scheduling. A flexible solution is a set of schedules following a structure defined by a partial order of jobs and a type of schedules. here, we consider active and non-delay schedules. The proposed structure allows the decision maker to dispose of some flexibility (a set of schedules instead of one schedule) that 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 is a function of (i) the best case performance providing the decision maker a lower bound of the performance, (ii) the worst case performance giving him a guarantee about how poorly the solution may perform, in both cases when following the considered structure. The worst cases correspond to new scheduling problems, in which a regular criterion must be maximized. We present new algorithms and/or new computational complexity results, in presence of: one machine, different release dates, precedence constraints and various criteria to be maximized. || Nous nous intéressons dans ce papier à l'évaluation de performance dans le pire des cas pour des solutions d'ordonnancement flexibles pour des problèmes d'ordonnancement à une machine. Une solution flexible est définie par un ordre partiel et par un type
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:38:03 AM
Last modification on : Friday, February 4, 2022 - 3:33:15 AM


  • HAL Id : inria-00099517, version 1



Mohamed Ali Aloulou, Marie-Claude Portmann, Mikhail Y. Kovalyov. Worst case performance evaluation of flexible solutions in single machine scheduling. Computing Engineering in Systems Applications - CESA'2003, Jul 2003, Lille, France, 7 p. ⟨inria-00099517⟩



Record views