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)||\sum T_i)\). 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 ensembles of both classic priority rules and the best rules obtained by GP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Branke, J., Hildebrandt, T., Scholz-Reiter, B.: Hyper-heuristic evolution of dispatching rules: a comparison of rule representations. Evol. Comput. 23(2), 249–277 (2015)
Durasevic, M., Jakobovi, D., Kneževi, K.: Adaptive scheduling on unrelated machines with genetic programming. Appl. Soft Comput. 48, 419–430 (2016)
Gil-Gala, F., Mencía, C., Sierra, M., Varela, R.: Genetic programming to evolve priority rules for on-line scheduling on single machine with variable capacity. In: XVIII Conferencia de la Asociación Española para la Inteligencia Artificial, MAEB (2018)
Hart, E., Sim, K.: A hyper-heuristic ensemble method for static job-shop scheduling. Evol. Comput. 24(4), 609–635 (2016)
Hernández-Arauzo, A., Puente, J., Varela, R., Sedano, J.: Electric vehicle charging under power and balance constraints as dynamic scheduling. Comput. Ind. Eng. 85, 306–315 (2015)
Jakobović, D., Marasović, K.: Evolving priority scheduling heuristics with genetic programming. Appl. Soft Comput. 12(9), 2781–2789 (2012)
Kaplan, S., Rabadi, G.: Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times. Comput. Ind. Eng. 62(1), 276–285 (2012)
Koulamas, C.: The total tardiness problem: review and extensions. Oper. Res. 42, 1025–1041 (1994)
Mencía, C., Sierra, M., Mencía, R., Varela, R.: Evolutionary one-machine scheduling in the context of electric vehicles charging. Integr. Comput.-Aided Eng. 26(1), 1–15 (2019)
Sang-Oh Shim, S.O., Kim, Y.D.: Scheduling on parallel identical machines to minimize total tardiness. Eur. J. Oper. Res. 177(1), 135–146 (2007)
Acknowledgements
This research has been supported by the Spanish Government under research project TIN2016-79190-R and by Principality of Asturias under grant IDI/2018/000176.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Gil-Gala, F.J., Varela, R. (2019). Genetic Algorithm to Evolve Ensembles of Rules for On-Line Scheduling on Single Machine with Variable Capacity. In: Ferrández Vicente, J., Álvarez-Sánchez, J., de la Paz López, F., Toledo Moreo, J., Adeli, H. (eds) From Bioinspired Systems and Biomedical Applications to Machine Learning. IWINAC 2019. Lecture Notes in Computer Science(), vol 11487. Springer, Cham. https://doi.org/10.1007/978-3-030-19651-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-19651-6_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-19650-9
Online ISBN: 978-3-030-19651-6
eBook Packages: Computer ScienceComputer Science (R0)