Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times

SUMMARY

We present a family of rolling horizon heuristics for minimizing maximum lateness on parallel identical machines in the presence of sequence dependent setup times and dynamic job arrivals. This problem arises as a subproblem in a decomposition procedure for more complex job shop scheduling problems. The procedures solve a series of single machine subproblems to optimality and implement only part of the solution. Extensive computational experiments show that these methods significantly outperform dispatching rules combined with local search methods, both on average and in the worst case. Their performance advantage is particularly pronounced when there is high competition for machine capacity.