Authors: Sabrina Merchichi; Menouar Boulif
Addresses: LIMOSE Laboratory, Computer Science Department, Faculty of Sciences, University M'Hamed Bougara of Boumerdes, Boumerdès, Independency Avenue, 35000 Algeria ' Computer Science Department, Faculty of Sciences, University M'Hamed Bougara of Boumerdes, Boumerdès, Independency Avenue, 35000 Algeria
Abstract: This paper deals with the manufacturing cell formation (MCF) problem, which is based on group technology (GT) principles, by using a graph-theoretic model. Due to the exponential nature of the problem, various heuristics and meta-heuristics have been proposed to solve it. However, only few studies have attempted to develop exact algorithms. In this paper, we develop two B&B algorithms, taking into account the actual constraints of production. The first algorithm is based on the notion of co-cycles (cuts) in the generation of solutions. The second has a similar structure, except that it is improved by using the constraints. The obtained results of the two algorithms are reported for medium-sized instances. [Received 6 December 2013; Revised 10 March 2014; Accepted 3 August 2014]
Keywords: group technology; manufacturing cells; cell formation; MCF; graph partitioning; branch and bound; graph theory; production constraints; cellular manufacturing.
European Journal of Industrial Engineering, 2015 Vol.9 No.6, pp.717 - 743
Received: 08 May 2021
Accepted: 12 May 2021
Published online: 25 Jan 2016 *