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 <>
Submitted on : Tuesday, September 26, 2006 - 9:38:03 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM


  • 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