Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times

Publisher Website
Google Scholar
Abstract
We present a family of rolling horizon heuristics to minimize maximum lateness on a single machine in the presence of sequence-dependent setup times. This problem occurs as a subproblem in a decomposition procedure for more complicated job shop scheduling problems. The procedures solve a sequence of subproblems to optimality with a branch and bound algorithm and implements only part of the solution obtained. The size and number of the subproblems are controlled by algorithm parameters. Extensive computational experiments show that these procedures outperform myopic dispatching rules by an order of magnitude, both on average and in the worst case, in very reasonable computation times.

This publication has 18 references indexed in Scilit: