Paper Info
Title
Optimal level schedules for mixed-model, multi-level just-in-time assembly systems
Abstract
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.
Year
DOI
Venue
1997
10.1023/A:1018985029260
Annals OR
Keywords
Field
DocType
Schedule Problem,Dynamic Programming,Optimal Schedule,Programming Algorithm,Assembly System
Dynamic programming,Mathematical optimization,Computer science,Scheduling (computing),Assembly systems,Filter (signal processing),Mixed model,Schedule,Dynamic priority scheduling,State space
Journal
Volume
Issue
ISSN
69
0
1572-9338
Citations 
PageRank 
References 
11
2.11
1
Authors
3
Name
Order
Citations
PageRank
Wieslaw Kubiak154062.61
George Steiner2375.51
Julian Scott Yeomans3367.08