Decomposition methods for large job shops
Loading...
Date
2001
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
PERGAMON-ELSEVIER SCIENCE LTD
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.
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.
Description
Keywords
scheduling, job shop, rolling horizon, SHIFTING BOTTLENECK PROCEDURE, SCHEDULING PROBLEM, WEIGHTED TARDINESS, ALGORITHM, SEARCH