# Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine

RAIRO - Operations Research (2010)

- 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 35.2 (2010): 165-187. <http://eudml.org/doc/197824>.

@article{Chrétienne2010,

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(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(n3logn) 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},

keywords = { Scheduling; algorithm; complexity.; scheduling; complexity},

language = {eng},

month = {3},

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/197824},

volume = {35},

year = {2010},

}

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

DA - 2010/3//

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(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(n3logn) 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.; scheduling; complexity

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

ER -

## References

top- 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.90033
- K.R. Baker and G.D. Scudder, Sequencing with Earliness-Tardiness Penalties: A Review. Oper. Res.38 (1989) 22-36. Zbl0699.90052
- 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
- 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
- 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
- A. Federgruen and G. Mosheiov, Single-Machine Scheduling Problems with General Breakdowns, Earliness and Tardiness Costs. Oper. Res.45 (1997) 66-71. Zbl0892.90100
- 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.90060
- 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.90037
- 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.90037

## NotesEmbed ?

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