LIP6 1999/007
- Reports
Minimisation du coût de l'avance et du retard d'une séquence de tâches sur une machine - Ph. Chrétienne
- 27 pages - 04/06/1999- document en - http://www.lip6.fr/lip6/reports/1999/lip6.1999.007.ps.gz - 91 Ko
- Contact : Philippe.Chretienne (at) nulllip6.fr
- Ancien Thème : SYSDEF
- Keywords : one-machine scheduling, algorithm, complexity
- Publisher : Valerie.Mangin (at) nulllip6.fr
Assume that n tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey et al. have proposed a nice O(nlog n) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to the case of asymmetric and task-independent cost without increasing its worst-case complexity. For the general case of asymmetric and task-dependent costs, we propose an O(n3 log n) algorithm based on a strong dominance property that yields to efficiently model the scheduling problem as a minimum cost path in a valued directed acyclic graph.