We study a single-machine scheduling problem and we solve it with a branch-and-bound algorithm.

What is it about?

The paper is about a special type of single-machine scheduling problem arising in practice. A set of jobs is given to be executed by a machine. Each job has a given processing time and jobs can neither overlap in time nor being interrupted and resumed. For each job we are given a deadline to be strictly respected and a soft due date that expresses a preference about the job completion time. The tardiness of a job is the difference between its completion time ane its due date, if this difference is positive. It is allowed to discard some jobs, paying a penalty for that. The objective to be minimized is given by the sum of two terms: the total tardiness and the total penalties.

Featured Image

Why is it important?

The relevance of this paper consists of providing an exact optimization problem for this type of scheduling problem.