A Branch and Bound Algorithm for the Cell Formation Problem

被引：1
作者：
Utkina, Irina [1 ]
Batsyn, Mikhail [1 ]
机构：
[1] Natl Res Univ, Lab Algorithms & Technol Networks Anal, Higher Sch Econ, 136 Rodionova Str, Nizhnii Novgorod, Russia
来源：
MODELS, ALGORITHMS AND TECHNOLOGIES FOR NETWORK ANALYSIS, NET 2014 | 2016年 / 156卷
关键词：
Cell formation problem; Branch and bound algorithm; NP-hard problems; Combinatorial optimization; Upper bound; Exact solution; SIMILARITY COEFFICIENT METHOD; GROUP-TECHNOLOGY; MATRICES;
D O I：
10.1007/978-3-319-29608-1_7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems of the 35 popular benchmark instances from the literature.
引用
收藏
页码：115 / 124
页数：10
相关论文
共 22 条
123