An efficient ILP formulation for the single machine scheduling problem

This paper considers the problem of scheduling n 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 (L-max). Experiments have been performed by means of a commercial solver that show that this formulation is effective on large problem instances. A comparison with the branch-and-bound procedure of Carlier is provided.