Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Nadia Brauner 1 Gerd Finke 1 Yakov Shafransky 2 Dzmitry Sledneu 3
1 G-SCOP_ROSP - ROSP
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : The well-known O(n2) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was devel- oped to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result con- cerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an addi- tional numerical parameter, for which only an interval of possible values is known. For this problem we derive an O(n2) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.
Type de document :
Article dans une revue
Journal of Scheduling, Springer Verlag, 2016, 19 (4), pp.401-408. 〈10.1007/s10951-014-0413-x〉
Liste complète des métadonnées

http://hal.univ-grenoble-alpes.fr/hal-01107557
Contributeur : Nadia Brauner <>
Soumis le : mercredi 21 janvier 2015 - 09:21:50
Dernière modification le : lundi 30 avril 2018 - 15:02:01

Identifiants

Collections

Citation

Nadia Brauner, Gerd Finke, Yakov Shafransky, Dzmitry Sledneu. Lawler’s minmax cost algorithm: optimality conditions and uncertainty. Journal of Scheduling, Springer Verlag, 2016, 19 (4), pp.401-408. 〈10.1007/s10951-014-0413-x〉. 〈hal-01107557〉

Partager

Métriques

Consultations de la notice

243