LIP6 1999/032
- Reports
Ordonnancement en présence de dates souhaitées et de dates impératives - F. Sourd, W. Nuijten
- 22 pages - 12/20/1999- document en - http://www.lip6.fr/lip6/reports/1999/lip6.1999.032.ps.gz - 130 Ko
- Contact : Francis.Sourd (at) nulllip6.fr
- Ancien Thème : SYSDEF
- Keywords : scheduling, release dates, deadlines, due dates, tails, minimax objective function, shop scheduling problem, lower bound
- Publisher : Valerie.Mangin (at) nulllip6.fr
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.
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.