A branch and bound approach for single machine scheduling with earliness and tardiness penalties

An n job, single machine scheduling problem in which each job has a distinct due date, di, is studied in this paper. The objective is to determine an optimal schedule π0s for a set of jobs, S, such that the total absolute deviation of the schedule is minimized. This objective function is based on the due date value and on the earliness or tardiness of each job in the selected sequence. This paper presents a bounding scheme for the calculation of different lower bounds based on the overlap elimination procedure on a Just-In-Time schedule. Properties and theorems of the overlap elimination procedure are also provided. Finally, a numerical example is illustrated and some extensions of the approach are also discussed.