Article ID: | iaor1989328 |
Country: | United States |
Volume: | 21 |
Issue: | 2 |
Start Page Number: | 144 |
End Page Number: | 152 |
Publication Date: | Jun 1989 |
Journal: | IIE Transactions |
Authors: | Thomas L. Joseph, McClain John O., Weiss Elliott N. |
Keywords: | scheduling, planning |
In this paper the authors present a decomposition approach to solve large scale linear programming models for production scheduling when there are multiple capacity-constrained facilities. The formulation assumes that there are no initial inventories, and hence is most useful in a planning environment where the current shop status is not the primary concern. The approach can be implemented as an exact procedure or with heuristic stopping rules. We determine problem characteristics for which the decomposition approach is faster than LP, so that very large problems could be solved. Problem difficulty is found to be related to size and tightness of the capacity constraints. Quality-of-solution versus CPU time tradeoffs are given for various stopping rules. Finally, the authors discuss the potential importance of this formulation and approach in manufacturing problems.