Decomposition methods for large job shops

Abstract

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.

Scope and purpose

There has been a significant amount of research focused on the scheduling of a job shop, either minimizing the makespan or the tardiness. Although the results for small-size problems are satisfactory, there has been no approach as for yet middle- and large-size problems. This paper presents a heuristic that decomposes the problems on a time window basis, solving each subproblem using a shifting bottleneck heuristic. Its results for a due-date-related objective function are promising. (C) 2000 Elsevier Science Ltd. All rights reserved.