Block Angular Structures and the Loading Problem in Flexible Manufacturing Systems

Panagiotis Kouvelis and Hau L. Lee
Additional contact information
Panagiotis Kouvelis: The University of Texas at Austin, Austin, Texas
Hau L. Lee: Stanford University, Stanford, California

Operations Research, 1991, vol. 39, issue 4, 666-676

Abstract: Loading problems of Flexible Manufacturing Systems (FMSs) have usually been formulated as an integer program with nonlinear constraints for tool magazine capacities. The nonlinearity and integer nature of the problem results in the loading problem being difficult to solve. Conventional branch-and-bound methods have been proposed, but again the solution time can easily be excessive for moderate sized problems. In this paper, we present an alternative formulation of the FMS loading problem. Such a formulation defines more decision variables, but is able to avoid nonlinearity of the constraints. It also includes the time availabilities of the machines as additional constraints. The main feature of the formulation is that it exhibits a block angular structure. By exploiting this special structure, an efficient branch-and-bound algorithm can be developed. This algorithm has the attractive feature that the bounds of the branches can be computed through simple procedures based on the solution of linear knapsack problems. Some computational results of the algorithm are also presented.

Keywords: integer programming: algorithms; production/scheduling: flexible manufacturing; planning (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.666 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:4:p:666-676

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().