Abstract
Scheduling problems are very hard computational tasks with several applications in multitude of domains. In this work we solve a practical problem motivated by a real industry situation, in which we apply a genetic algorithm for finding an acceptable solution in a very short time interval. The main novelty introduced in this work is the use of a priority based chromosome codification that determines the precedence of a task with respect to other ones, permitting to introduce in a very simple way all problem constraints, including setup costs and workforce availability. Results show the suitability of the approach, obtaining real time solutions for tasks with up to 50 products.
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
Allahverdi, A., Ng, C., Cheng, T., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985–1032 (2008)
Cičková, Z., Števo, S.: Flow shop scheduling using differential evolution. Manag. Inf. Syst. 5(2), 8–13 (2010)
Gonzalez, T., Sahni, S.: Flowshop and jobshop schedules: complexity and approximation. Oper. Res. 26(1), 36–52 (1978)
Ham, M., Lee, Y.H., Fowler, J.W.: Integer programming-based real-time scheduler in semiconductor manufacturing. In: Proceedings of the 2009 Winter Simulation Conference (WSC), pp. 1657–1666 (2009)
Huang, I., Li, B.: A genetic algorithm using priority-based encoding for routing and spectrum assignment in elastic optical network, pp. 5–11 (2015)
Koblasa, F., Sahni, F.M., Vavruška, J.: Evolution algorithm for job shop scheduling problem constrained by the optimization timespan. Appl. Mech. Mater. 309, 36–52 (2013)
Levner, E., Kats, V., Alcaide López De Pablo, D., Cheng, T.: Complexity of cyclic scheduling problems: a state-of-the-art survey. Comput. Ind. Eng. 59(2), 352–361 (2010)
Mesghouni, K., Hammadi, S., Borne, P.: Evolutionary algorithms for job-shop scheduling. Appl. Math. Comput. Sci. 14(1), 91–103 (2004)
Nowling, R., Mauch, H.: Priority encoding scheme for solving permutation and constraint problems with genetic algorithms and simulated annealing, pp. 810–815 (2010)
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 3rd edn. Springer Publishing Company Incorporated, Heidelberg (2008)
Ribeiro, F., De Souza, S., Souza, M., Gomes, R.: An adaptive genetic algorithm to solve the single machine scheduling problem with earliness and tardiness penalties (2010)
Acknowledgements
The authors acknowledge support through grants TIN2014-58516-C2-1-R and TIN2014-58516-C2-2-R from MICINN-SPAIN which include FEDER funds.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Subirats, J.L. et al. (2017). Solving Scheduling Problems with Genetic Algorithms Using a Priority Encoding Scheme. In: Rojas, I., Joya, G., Catala, A. (eds) Advances in Computational Intelligence. IWANN 2017. Lecture Notes in Computer Science(), vol 10305. Springer, Cham. https://doi.org/10.1007/978-3-319-59153-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-59153-7_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59152-0
Online ISBN: 978-3-319-59153-7
eBook Packages: Computer ScienceComputer Science (R0)