Article contents
Minimizing the Earliness and Tardiness Costof a Sequence of Tasks on a Single Machine
Published online by Cambridge University Press: 15 August 2002
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(n3 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.
Keywords
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2001
References
- 2
- Cited by