Repairing infeasibility in scheduling via genetic algorithms

Autores: Raul Mencia Cascallana, Carlos Mencía Cascallana , Ramiro Alberto Varela Benvenuto
Localización: From Bioinspired Systems and Biomedical Applications to Machine Learning: 8th International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2019, Almería, Spain, June 3–7, 2019, Proceedings, Part II / coord. por Hojjat Adeli; José Manuel Ferrández Vicente (dir. congr.) , José Ramón Álvarez Sánchez (dir. congr.) , Félix de la Paz López (dir. congr.) , Francisco Javier Toledo Moreo (dir. congr.), 2019, ISBN 978-3-030-19651-6, págs. 254-263
Idioma: inglés
Texto completo no disponible (Saber más ...)
Resumen
- Scheduling problems arise in an ever increasing number ofapplication domains. Although efficient algorithms exist for a variety of such problems, sometimes it is necessary to satisfy hard constraints that make the problem unfeasible. In this situation, identifying possible ways of repairing infeasibility represents a task of utmost interest. We consider this scenario in the context of job shop scheduling with a hard makespan constraint and address the problem of finding the largest possible subset of the jobs that can be scheduled within such constraint. To this aim, we develop a genetic algorithm that looks for solutions in the searchspace defined by an efficient solution builder, also proposed in the paper. Experimental results show the suitability of our approach.