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

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

0.00 Avg rating0 Votes
Article ID: iaor20053114
Country: France
Volume: 35
Issue: 2
Start Page Number: 165
End Page Number: 187
Publication Date: Apr 2001
Journal: RAIRO Operations Research
Authors:
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. Garvey 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(n3 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.

Reviews

Required fields are marked *. Your email address will not be published.