Title: Constraint-driven exact algorithm for the manufacturing cell formation problem

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.

DOI: 10.1504/EJIE.2015.074379

European Journal of Industrial Engineering, 2015 Vol.9 No.6, pp.717 - 743

Published online: 26 Jan 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article