A branch-and-bound algorithm for the cell formation problem

Abstract

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.

Keywords:

• cell formation problem
• biclustering
• branch-and-bound
• Dinkelbach approach
• exact solution

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is conducted in LATNA Laboratory, NRU HSE and supported by RSF [grant number 14-41-00039].