A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem

摘要

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.