Scheduling a single machine to minimize a regular objective function under setup constraints

Motivated by industrial applications, we study the scheduling situation in which a set of jobs subjected to release dates and deadlines are to be performed on a single machine. The objective is to minimize a regular sum objective function ∑ifi where fi(Ci) corresponds to the cost of the completion of job Ji at time Ci. On top of this, we also take into account setup times and setup costs between families of jobs as well as the fact that some jobs can be “unperformed” to reduce the load of the machine. We introduce lower bounds and dominance properties for this problem and we describe a Branch and Bound procedure with constraint propagation. Experimental results are reported.