Efficient Parallel Sorting for Migrating Birds Optimization When Solving Machine-Part Cell Formation Problems
Authors:
Open Access
- 31 March 2016
- journal article
- research article
- Published by Wiley in Scientific Programming
- Vol. 2016, 1-39
Abstract
The Machine-Part Cell Formation Problem (MPCFP) is a NP-Hard optimization problem that consists in grouping machines and parts in a set of cells, so that each cell can operate independently and the intercell movements are minimized. This problem has largely been tackled in the literature by using different techniques ranging from classic methods such as linear programming to more modern nature-inspired metaheuristics. In this paper, we present an efficient parallel version of the Migrating Birds Optimization metaheuristic for solving the MPCFP. Migrating Birds Optimization is a population metaheuristic based on the V-Flight formation of the migrating birds, which is proven to be an effective formation in energy saving. This approach is enhanced by the smart incorporation of parallel procedures that notably improve performance of the several sorting processes performed by the metaheuristic. We perform computational experiments on 1080 benchmarks resulting from the combination of 90 well-known MPCFP instances with 12 sorting configurations with and without threads. We illustrate promising results where the proposal is able to reach the global optimum in all instances, while the solving time with respect to a nonparallel approach is notably reduced.Keywords
Funding Information
- Comisión Nacional de Investigación Científica y Tecnológica (11130459, 1140897, 1130455)
- Comisión Nacional de Investigación Científica y Tecnológica (11130459, 1140897, 1130455)
- Comisión Nacional de Investigación Científica y Tecnológica (11130459, 1140897, 1130455)
- Pontificia Universidad Católica de Valparaíso (11130459, 1140897, 1130455)
This publication has 39 references indexed in Scilit:
- Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research, 2012
- Collaborative particle swarm optimization with a data mining technique for manufacturing cell designExpert Systems with Applications, 2010
- Variable neighbourhood search: methods and applicationsAnnals of Operations Research, 2009
- Organized flight in birdsAnimal Behaviour, 2009
- A one-step tabu search algorithm for manufacturing cell designJournal of the Operational Research Society, 1999
- Cell formation in group technology: Review, evaluation and directions for future researchComputers & Industrial Engineering, 1998
- A Jinear formulation of the machine-part cell formation problemInternational Journal of Production Research, 1991
- The facets of group technology and their impacts on implementation—A state-of-the-art surveyOmega, 1985
- Optimization by Simulated AnnealingScience, 1983
- Energy savings through formation flight? A re-examination of the vee formationJournal of Theoretical Biology, 1981