Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine

Chrétienne, Philippe

RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 165-187.

Supposons que $n$ tâches doivent être exécutées par une machine dans un ordre fixé a priori. On connaît pour chaque tâche sa durée, la date souhaitée de son exécution et les coûts unitaires associés d’avance et de retard. On cherche à allouer à chaque tâche une date d’exécution de sorte que le coût total des avances et des retards soit minimum. Un algorithme de complexité $O(nlogn)$ a été proposé par Garey et al. pour le cas particulier de coûts unitaires. Nous proposons d’abord un algorithme de complexité $O(n^{2}logn)$ qui étend l’algorithme Garey et al. au cas de coûts asymétriques indépendants des tâches. Pour le cas général de coûts asymétriques dépendants des tâches, nous proposons un algorithme de complexité $O(n^{3}logn)$ fondé sur une propriété de dominance permettant de ramener le problème à la recherche d’un chemin de coût minimum dans un graphe valué sans circuit.

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(nlogn)$ 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(n^{3}logn)$ algorithm based on a strong dominance property that yields to model the scheduling problem as a minimum cost path in a valued directed acyclic graph.

[1] M.R. Garey, R.E. Tarjan and G.T. Wilfong, One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13 (1988) 330-348. | MR | Zbl

[2] K.R. Baker and G.D. Scudder, Sequencing with Earliness-Tardiness Penalties: A Review. Oper. Res. 38 (1989) 22-36. | MR | Zbl

[3] V. Gordon, J.M. Proth and C. Chu, A State-of-the-Art Survey of Due Date Assignment and Scheduling Research: Common Due Date. Rapport de recherche INRIA, 3454, Theme 4 (1998).

[4] V. Gordon, J.M. Proth and C. Chu, A State-of-the-Art Survey of Due Date Assignment and Scheduling Research: SLK, TWK and Other Due Date Assignment Models. Rapport de recherche INRIA, 3537, Theme 4 (1998).

[5] J.A. Hoogeveen and S.L. Van De Velde, A branch-and-Bound Algorithm for Single-Machine Earliness-Tardiness Scheduling with Idle Time. INFORMS J. Comput. 8 (1996) 402-412. | Zbl

[6] A. Federgruen and G. Mosheiov, Single-Machine Scheduling Problems with General Breakdowns, Earliness and Tardiness Costs. Oper. Res. 45 (1997) 66-71. | Zbl

[7] A. Federgruen and G. Mosheiov, Greedy Heuristics for Single-Machine Scheduling Problems with General Earliness and Tardiness Costs. Oper. Res. Lett. 16 (1994) 199-208. | MR | Zbl

[8] N.G. Hall, W. Kubiak and S.P. Sethi, Earliness-Tardiness Scheduling Problems I. Deviation of Completion Times about a Restrictive Common Due Date. Oper. Res. 39 (1991) 102-110. | MR | Zbl

[9] N.G. Hall, W. Kubiak and S.P. Sethi, Earliness-Tardiness Scheduling Problems II. Deviation of Completion Times about a Restrictive Common Due Date. Oper. Res. 39 (1991) 102-110. | MR | Zbl