Achieving high cell utilisation via hybrid MILP models using restriction
提出一种紧凑的混合整数线性规划模型，通过减少变量和约束来最小化空隙，并结合启发式与精确搜索的两阶段混合方法，高效求解中大型单元形成问题，实现高单元利用率。
Constructing compact and independent cells is very important as it greatly affects the achievement of high cell utilisation (CU), which is one of the most crucial goals in the cell formation (CF) procedure. Void minimisation has been considered as an alternative for CU maximisation. Nevertheless, few efficient models for void minimisation have been developed with the compact formulation by which medium- or larger size problem instances can be solved to optimality or near-optimality in an acceptable time. In this paper, a compact mixed-integer linear programming (MILP) model with much fewer binary variables and constraints than the previous MILP models for minimising voids is presented by employing an efficient linearisation technique. Key properties of the proposed MILP models are analysed. To obtain more accurate approximation of CU, the void minimisation model is extended by incorporating exceptional elements. Next, a two-phase hybrid approach is introduced that integrates a p-median-based heuristic with an exact search algorithm to achieve near-optimal solutions. Computational results on a range of CF instances demonstrate the efficiency and effectiveness of the proposed models and hybrid solution method.