Genetic algorithm to evolve ensembles of rules for on-line scheduling on single machine with variable capacity

  1. Francisco Gil-Gala
  2. Ramiro Varela
Book:
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.)

Publisher: Springer Suiza

ISBN: 978-3-030-19651-6

Year of publication: 2019

Pages: 223-233

Type: Book chapter

Abstract

On-line scheduling is often required in real life situations.This is the case of the one machine scheduling with variable capacity and tardiness minimization problem, denoted (1, Cap(t)||Ti). This problem arose from a charging station where the charging periods for large fleets of electric vehicles (EV) must be scheduled under limited power and other technological constraints. The control system of the charging station requires solving many instances of this problem on-line.The characteristics of these instances being strongly dependent on the load and restrictions of the charging station at a given time. In this paper, the goal is to evolve small ensembles of priority rules such that for any instance of the problem at least one of the rules in the ensemble has high chance to produce a good solution. To do that, we propose a Genetic Algorithm (GA) that evolves ensembles of rules from a large set of rules previously calculated by a Genetic Program (GP). We conducted an experimental study showing that the GA is able to evolve ensembles or rules covering instances with different characteristics and so they outperform ensemblesof both classic priority rules and the best rules obtained by GP.