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
Type de document :
Communication dans un congrès
Computing Engineering in Systems Applications - CESA'2003, Jul 2003, Lille, France, 7 p, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099517
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:38:03
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099517, version 1

Collections

Citation

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, 2003. 〈inria-00099517〉

Partager

Métriques

Consultations de la notice

123