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

Chré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 -