Maximization Problems in Single Machine Scheduling

Mohamed Ali Aloulou 1 Mikhail Y. Kovalyov 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 : Problems of scheduling n jobs on a single machine to maximize regular objective function are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Only semi-active schedules are of interest, i.e. those for which the jobs cannot be shifted to start earlier without changing the job sequence or violating the feasibility. Such maximization problems arise in predictive-reactive scheduling. Their solutions are used to evaluate the worst-case performance of a set of schedules characterized by a partial order. The most general problem of maximizing maximum cost is solved in O(n3) time. When all release times are equal to zero, it is shown that the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization couterpart with precedence constraints reversed wrt the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n-1 jobs available at the same time. Algorithmic and computational complexity results for several maximization problems follow from these statements. || On étudie des problèmes de maximisation de critères réguliers pour des problèmes d'ordonnancement à une machine. Des contraintes de précédences sur l'ensemble des travaux et différentes dates de disponibilités sont considérées. Seuls les ordonnancements s
Type de document :
Article dans une revue
Annals of Operations Research, Springer Verlag, 2004, 129 (1-4), pp.21-32
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:12:48
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00099946, version 1



Mohamed Ali Aloulou, Mikhail Y. Kovalyov, Marie-Claude Portmann. Maximization Problems in Single Machine Scheduling. Annals of Operations Research, Springer Verlag, 2004, 129 (1-4), pp.21-32. 〈inria-00099946〉



Consultations de la notice