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

RAIRO - Operations Research - Recherche Opérationnelle (2001)

- Volume: 35, Issue: 2, page 165-187
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topChrétienne, Philippe. "Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine." RAIRO - Operations Research - Recherche Opérationnelle 35.2 (2001): 165-187. <http://eudml.org/doc/105241>.

@article{Chrétienne2001,

abstract = {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(n\log 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(n^3\log n)$ 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.},

author = {Chrétienne, Philippe},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {scheduling; algorithm; complexity},

language = {eng},

number = {2},

pages = {165-187},

publisher = {EDP-Sciences},

title = {Minimizing the earliness and tardiness cost of a sequence of tasks on a single machine},

url = {http://eudml.org/doc/105241},

volume = {35},

year = {2001},

}

TY - JOUR

AU - Chrétienne, Philippe

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

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2001

PB - EDP-Sciences

VL - 35

IS - 2

SP - 165

EP - 187

AB - 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(n\log 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(n^3\log n)$ 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.

LA - eng

KW - scheduling; algorithm; complexity

UR - http://eudml.org/doc/105241

ER -

## References

top- [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. Zbl0671.90033MR942622
- [2] K.R. Baker and G.D. Scudder, Sequencing with Earliness-Tardiness Penalties: A Review. Oper. Res. 38 (1989) 22-36. Zbl0699.90052MR1041230
- [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). Zbl1009.90054
- [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). Zbl1009.90054
- [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. Zbl0884.90102
- [6] A. Federgruen and G. Mosheiov, Single-Machine Scheduling Problems with General Breakdowns, Earliness and Tardiness Costs. Oper. Res. 45 (1997) 66-71. Zbl0892.90100
- [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. Zbl0823.90060MR1306704
- [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. Zbl0762.90037MR1132384
- [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. Zbl0762.90037MR1132384

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.