A splitting-up approach to simplify job-shop scheduling problems

Abstract

In this paper we propose a scheduling algorithm based on splitting up the problem into separate yet linked subproblems. We develop a heuristic algorithm to manage the remaining links between the scheduling subproblems obtained as a result of the splitting process. The complexity of the computation and the performance of the algorithms are examined and numerical examples are given to illustrate these algorithms.