Displaying similar documents to “Optimal starting times for a class of single machine scheduling problems with earliness and tardiness penalties”

An efficient ILP formulation for the single machine scheduling problem

Cyril Briand, Samia Ourari, Brahim Bouzouia (2010)

RAIRO - Operations Research

Similarity:

This paper considers the problem of scheduling jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. On the basis of analytical and numerical dominance conditions, an efficient integer linear programming formulation is proposed for this problem, aiming at minimizing the maximum lateness ( ). Experiments have been performed by means of a commercial solver that show that this formulation...

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

Philippe Chrétienne (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

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...