A hybrid iterated local search and variable neighborhood descent heuristic applied to the cell formation problem

摘要

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. (C) 2015 Elsevier Ltd. All rights reserved.