Scheduling with tails and deadlines

F. Sourd, W. Nuijten

LIP6 1999/032: Rapport de Recherche LIP6 / LIP6 research reports
22 pages - Décembre/December 1999 - Document en anglais.

PostScript : 127 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Ordonnancement en présence de dates souhaitées et de dates impératives
Titre anglais : Scheduling with tails and deadlines

Résumé : Ce papier traite des problèmes d'ordonnancement d'opérations avec une queue. Ces queues sont d'ordinaire utilisées dans la littérature pour modéliser des dates d'échéances, qu'elles soient impératives ou simplement souhaitées. Nous montrons qu'il peut être intéressant, particulièrement dans les problèmes d'ateliers, de considérer des opérations ayant à la fois une date de fin impérative et une date souhaitée, modélisée par une queue. Nous faisons ensuite un tour d'horizon des principaux problèmes à une machine et à machines parallèles pour voir quels sont ceux qui peuvent être résolus en temps polynomial en présence de dates de fin et de queues. Nous montrons que que ces deux données peuvent être modélisées par un fonction objectif fmax de type 'minimax'. De cette manière, plusieurs problèmes peuvent être résolus en temps quadratique. Mais, en regardant les propriétés particulières de ces problèmes, on arrive à montrer qu'ils peuvent être résolus en O(nlogn). Nous montrons également que P|pj=1|rj|fmax peut être résolus en temps O(n^2).

Abstract : This paper discusses scheduling problems of operations with tails. While tails are usually used in the literature to model due dates or deadlines, we show it may be interesting to consider tails and deadlines as two different things, especially in shop problems. Then, we review classical one machine and parallel machine problems to show which problems can be still solved in polynomial time in presence of tails and deadlines. We show that both deadlines and tails can efficiently be modeled by a minimax objective function fmax. In this way, several problems can be solved in quadratic time but, by considering the
specific properties of tails and deadlines and introducing specific data structures, we also show that these problems can be solved in O(nlogn) time. We also show that P|pj=1,rj|fmax can be solved in O(n^2) time.

Mots-clés : ordonnancement, dates de début, dates de fin souhaitée, dates de fin impératives, problèmes d'ateliers, borne inférieure

Key-words : scheduling, release dates, deadlines, due dates, tails, minimax objective function, shop scheduling problem, lower bound

Publications internes LIP6 1999 / LIP6 research reports 1999

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr