Rapport de Recherche LIP6 /
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
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.
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