Article ID: | iaor19971817 |
Country: | Netherlands |
Volume: | 69 |
Issue: | 1 |
Start Page Number: | 241 |
End Page Number: | 259 |
Publication Date: | Jan 1997 |
Journal: | Annals of Operations Research |
Authors: | Steiner George, Kubiak Wieslaw, Yeomans Julian Scott |
Keywords: | scheduling |
Solving the level (or balanced) schedule problem is the most important scheduling goal for just-in-time production assembly systems. No previous methods have been presented for determining optimal balanced schedules in multi-level facilities. In this paper, it is shown that the multi-level, min-max problem is NP-hard in the strong sense. A dynamic programming algorithm (DP) is developed for both the min-max and min-sum problems which, for the first time, permits optimal schedules to be determined for large, multi-level problems. The time and space requirements of the DP are analyzed and several techniques for reducing the DP’s computational requirements are described. A filtering scheme is proposed to eliminate dominated solutions from a problem’s potentially vast state space. Extensive computational testing of the min-max algorithm is reported and the conclusions from this testing are presented.