Various Mathematical Programming Formulations for a General One Machine Sequencing Problem

The paper considers the problem of scheduling n jobs on a single machine to minimize the number of tardy jobs (or late jobs). Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Various mixed-integer linear programming formulations are presented and discussed. A new polynomial solvable case is also introduced. Keywords: scheduling, single machine, late jobs, integer programming. 1 Introduction Single machine scheduling models seem to be very simple but are very important for understanding and modeling multiple machines models. Minimizing the number of late jobs could appear a somewhat artificial problem but is often considered as a performance measure. Our study concerns the general one-machine scheduling problem denoted by 1jr j j P U j in the standard classification [Gra79]. A set J of n jobs has to be scheduled on a single machine in order to optimize a given criterion. In this proble..