Earliness–tardiness scheduling with setup considerations

The one-machine scheduling problem with sequence-dependent setup times and costs and earliness–tardiness penalties is addressed. A time-indexed formulation of the problem is presented as well as as different relaxations that give lower bounds of the problem. Then, a branch-and-bound procedure based on one of these lower bounds is presented. The efficiency of this algorithm also relies on new dominance rules and on a heuristic to derive good feasible schedules. Computational tests are finally presented.