Decomposition methods for large job shops

A rolling horizon heuristic is presented for large job shops, in which the total weighted tardiness must be minimized. The method divides a given instance into a number of subproblems, each having to correspond to a time window of the overall schedule, which are solved using a shifting bottleneck heuristic. A number of rules for defining each time window are derived. The method is tested by using instances up to 10 machines and 100 operations per machine, outperforming a shifting bottleneck heuristic that has been shown to generate close to optimal results.