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 inst ance into a number of subproblems, each having to correspond to a time wind ow of the overall schedule, which are solved using a shifting bottleneck he uristic. A number of rules for defining each time window are derived. The m ethod 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. Scope and purpose There has been a significant amount of research focused on the scheduling o f a job shop, either minimizing the makespan or the tardiness. Although the results for small-size problems are satisfactory, there has been no approa ch as for yet middle- and large-size problems. This paper presents a heuris tic that decomposes the problems on a time window basis, solving each subpr oblem using a shifting bottleneck heuristic. Its results for a due-date-rel ated objective function are promising. (C) 2000 Elsevier Science Ltd. All r ights reserved.