Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computional complexity

Mohamed Ali Aloulou 1 Mikhail Y. Kovalyov 2 Marie-Claude Portmann 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the deterministic problem of evaluating the worst case performance of flexible solutions in single machine scheduling. A flexible solution is a ste of schedules following a given structure determined by a partial order of jobs and a type of 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 on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimal and maximal values of the considered objective function. 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. || Nous étudions le problème déterministe d'évaluer la performance dans le pire des cas de solutions flexibles pour des problèmes d'ordonnancement à une machine. Une solution flexible est un ensemble d'ordonnancement donné par une structure qui comporte un p
Type de document :
[Intern report] A04-R-357 || aloulou04a, 2004, 22 p
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:15:49
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00100229, version 1



Mohamed Ali Aloulou, Mikhail Y. Kovalyov, Marie-Claude Portmann. Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computional complexity. [Intern report] A04-R-357 || aloulou04a, 2004, 22 p. 〈inria-00100229〉



Consultations de la notice