Title | ||
---|---|---|
A hybrid iterated local search and variable neighborhood descent heuristic applied to the cell formation problem |
Abstract | ||
---|---|---|
We propose a new heuristic algorithm for the Cell Formation Problem.The algorithm is based on Iterated Local Search with Variable Neighborhood Descent.Our method finds several optimal solutions for benchmark instances from literature.Our method improves solutions for instances with unknown optimal values. The Cell Formation Problem is an NP-hard optimization problem that consists of grouping machines into cells dedicated to producing a family of product parts, so that each cell operates independently and inter-cellular movements are minimized. Due to its high computational complexity, several heuristic methods have been developed over the last decades. Hybrid methods based on adaptations of popular metaheuristic techniques have shown to provide good performance in terms of solution quality. This paper proposes a new approach for solving the Cell Formation Problem using the group efficacy objective function. Our method is based on the Iterated Local Search metaheuristic coupled with a variant of the Variable Neighborhood Descent method that uses a random ordering of neighborhoods in local search phase. We consider two types of constraints on the minimum cell size, comparing them with several well-known algorithms in the literature. Computational experiments have been performed on 35 widely used benchmark instances with up to 40 machines and 100 parts. The proposed algorithm, besides obtaining solutions at least as good as any reported results, was able to find several optimal solutions and improve the group efficacy for some instances with unknown optima. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.eswa.2015.07.050 | Expert Systems with Applications |
Keywords | Field | DocType |
Metaheuristics,Cellular manufacturing,Group technology | Mathematical optimization,Heuristic,Cellular manufacturing,Computer science,Heuristic (computer science),Artificial intelligence,Local search (optimization),Optimization problem,Machine learning,Iterated local search,Metaheuristic,Computational complexity theory | Journal |
Volume | Issue | ISSN |
42 | 22 | 0957-4174 |
Citations | PageRank | References |
4 | 0.42 | 19 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ivan C. Martins | 1 | 20 | 2.14 |
Rian G. S. Pinheiro | 2 | 31 | 4.72 |
Fábio Protti | 3 | 357 | 46.14 |
Luiz Satoru Ochi | 4 | 474 | 34.62 |