Repairing infeasibility in scheduling via genetic algorithms

  1. Raúl Mencía
  2. Carlos Mencía
  3. Ramiro Varela
Llibre:
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
  1. José Manuel Ferrández Vicente (dir. congr.)
  2. José Ramón Álvarez-Sánchez (dir. congr.)
  3. Félix de la Paz López (dir. congr.)
  4. Javier Toledo Moreo (dir. congr.)
  5. Hojjat Adeli (coord.)

Editorial: Springer Suiza

ISBN: 978-3-030-19651-6

Any de publicació: 2019

Pàgines: 254-263

Tipus: Capítol de llibre

Resum

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.