Machine Allocation in Cellular Manufacturing Systems: An Application of Lagrangian Relaxation

The allocation of machines to part families in cellular manufacturing systems is formulated as 0–1 integer programming models, and a solution procedure based on Lagrangian relaxation is presented. A lternate relaxations are compared in terms of the quality of bounds and computational time. The application of the formulations is illustrated using large, randomly generated problems. Resume Le present article traite de divers modeles de program-mation par nombres entiers (0–1) de la fonction d'affectation de machines a des familles de pieces dans las systemes de fabrication cellulaires, et d'une methode de solution des problemes par relaxation lagrangienne. Des methodes utilisant d'autres types de relaxation sont egalement presentees afin d'etablir des compar aisons en cequi regarde la qualite des bornes et le temps de calcul. La methode de solution et les modeles proposees sont appliques a des problemes complexes generes de maniere aleatoire.