2016/03/15 by Irina Utkina, Utkina, Irina, Mikhail Batsyn +3
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Assembly Line Balancing Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1603.04597
arxiv created 2016/03/15 · openalex publication_date 2016/03/15 · arxiv updated 2016/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a fractional 0-1 programming problem arising in manufacturing. The problem consists in clustering of machines together with parts processed on these machines into manufacturing cells so that intra-cell processing of parts is maximized and inter-cell movement is minimized. This problem is called Cell Formation Problem (CFP) and it is an NP-hard optimization problem with Boolean variables and constraints and with a fractional objective function. Because of its high computational complexity there are a lot of heuristics developed for it. In this paper we suggest a branch and bound algorithm which provides exact solutions for the CFP with a variable number of cells and grouping efficacy objective function. This algorithm finds optimal solutions for 21 of the 35 popular benchmark instances from literature and for the remaining 14 instances it finds good solutions close to the best known.