- Título:
- ILS-ESP: An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem
- Autores:
- Angel A. Juan, Helena Ramalhinho-Lourenço, Manuel Mateo, Quim Castellà y Barry B. Barrios
- Fecha:
- Febrero 2012
- Resumen:
- From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be
used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop
Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP
algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most
effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their
performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common
sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new
operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased
randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is
attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding
poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed
computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and
compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art
metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top
ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number
generator.
- Palabras clave:
- Flow-Shop Problem, Scheduling, Randomized Algorithms, Iterated Local Search, Metaheuristics, GRASP
- Códigos JEL:
- C63; M11
- Área de investigación:
- Gestión de la Producción y de las Operaciones
Descargar el paper en formato PDF (306 Kb)