Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine
Philippe Chrétienne (2010)
RAIRO - Operations Research
Similarity:
Assume that 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 have proposed a nice log) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to...