An Hybrid Genetic Algorithm to Optimization of Flow Shop Scheduling Problems under Real Environments Constraints

Authors

  • Rodolfo Najarro Universidad Técnica de Cotopaxi
  • Ringo López Universidad Técnica de Cotopaxi
  • Ruth Elizabeth Racines Universidad Técnica Estatal de Quevedo
  • Amilkar Puris Universidad Técnica Estatal de Quevedo, Universidad Estatal de Milagro

DOI:

https://doi.org/10.29019/enfoqueute.v8n5.176

Keywords:

hybrid genetic algorithm, scheduling, flow shop, variable neighborhood search

Abstract

This paper aims to analyzing the effect of the inclusion of several constraints that have negative influence in the real manufacturing productions. For the solution of the scheduling problem treated in this paper, known as Flow Shop Scheduling, an efficient Genetic Algorithm is introduced combined with the Variable Neighborhood Search for problems of n tasks and m machines minimizing the total completion time or makespan. Release date, dependent setup-times and transport times are entered. These are common restrictions that can be found in multiple manufacturing environments where there are machines, tools, and a set of jobs must be processed in these, following the same flow pattern. The computational experiments carried out on a set of instances of problems of different sizes of complexity show that the proposed hybrid metaheuristic achieves high quality solutions comparable to the optimum ones reported.

Downloads

Download data is not yet available.

References

Ancâu, M. (2012). On Solving Flow Shop Scheduling Problems. Proceedings of the Romanian Academy, 13(1), 71-79.
Beasley, J. E. (1990). OR-Library. Retrieved January 17, 2014, from http://people.brunel.ac.uk/~mastjjb/jeb/info.html
Čičková, Z., y Števo, S. (2010). Flow Shop Scheduling using Differential Evolution. Management Information Systems, 5(2), 008-013.
Costa, A., Cappadona, F. A., y Fichera, A. (2017). A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem. Journal of Intelligent Manufacturing, 28(6), 1269-1282.
Chandrasekaran, S., Ponnambalam, S., Suresh, R., y Vijayakumar, N. (2007). Multi-objective particle swarm optimization algorithm for scheduling in flowshops to minimize makespan, total flowtime and completion time variance. Paper presented at the IEEE Congress on Evolutionary Computation.
Chaudhry, I. A., y Munem khan, A. (2012). Minimizing makespan for a no-wait flowshop using genetic algorithm. Sadhana, 36(6), 695-707.
Chie-Wun, C., Wen-Min, C., Chin-Min, L., y Muh-Cherng, W. (2012). A genetic algorithm for scheduling dual flow shops. Expert Systems with Applications(39), 1306–1314.
Dang, T., Dai, M., Salido, M. A., y Giret, A. (2016). Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 81, 82-95.
El-Bouri, A., Azizi, N., y Zolfaghari, S. (2007). A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling. European Journal of Operational Research, 177 1894–1910.
Fattahi, P., Hassan-Hosseini, S. M., Jolai, F., Tavakkoli-Moghaddam, R., y Tarantilis, C. D. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling(38), 119-134. doi: DOI:10.1016
Fernández-Viagas, V., Ruiz , R., y Framinan, J. M. (2016). A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation. European Journal of Operational Research, 09(55), 1-36. doi: 10.1016/j.ejor.2016.09.055
Fonseca, Y., Martínez, M., Bermúdez, J., y Méndez, B. (2015). A Reinforcement Learning Approach for Scheduling Problems. Revista Investigación Operacional, 36(3), 225-231.
Fonseca, Y., y Martínez, Y. (2017). Adapting a Reinforcement Learning Approach for the Flow Shop Environment with Sequence-Dependent Setup Time. Revista Cubana de Ciencias Informáticas, 11(1), 41-57.
Fonseca, Y., Martínez, Y., Figueredo, A. E., y Pernía, L. A. (2014). Behavior of the main parameters of the Genetic Algorithm for Flow Shop Scheduling Problems. Revista Cubana de Ciencias Informáticas, 8(1), 99-111.
Fonseca, Y., Martínez, Y., y Nowe, A. (2017). Q-Learning algorithm for m-machine, n-jobs Permutational Flow Shop Scheduling Problems to minimize makespan. Revista Investigación Operacional, 38(3), 281-290.
González, M. (2011). Soluciones Metaheurísticas al Job-Shop Scheduling Problem with Sequence-Dependent Setup Times. (Tesis Doctoral), Universidad de Oviedo, Oviedo.
Holland, J. H. (1975). Adaption in natural and artificial systems. Ann Arbor: University of Michigan Press.
Ishibuchi, H., Yoshida, T., y Murata, T. (2003). Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 7(2), 204–223.
Manne, A. S. (1960). On the Job-Shop Scheduling Problem. Operations Research, 8(2), 219.
Márquez, J. (2012). Genetic algorithm applied to scheduling in machine shops. Revista de Ingeniería Mecánica, 15(3), 201-212.
Medina, P., Cruz, E., y Hernad-Restrepo, J. (2008). Works programming in one machine uses a model Integer linear programming. Scientia et Technica, XIV(40), 111-116.
Mehmet, Y., y Betul, Y. (2014). Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, 45 119-135.
Murata, T., Ishibuchi, H., y Tanaka, H. (1996). Genetic algorithms for flowshop scheduling problems. Computers and industrial Engineering, 30, 1061–1071.
Naderi, B., Ruiz, R., y Zandieh, M. (2010). Algorithms for a realistic variant of flowshop scheduling. Computers & Operations Research(37), 236-246.
Neufeld, J. S., Gupta, J. N. D., y Busche, U. (2016). A comprehensive review of flowshop group scheduling literature. Computers and Operations Research.
Parviz, F., Seyed Mohammad, H. H., Fariborz, J., y Reza, T.-M. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling, 38, 119-134.
Pinedo, M. (2008). Scheduling Theory, Algorithms, and Systems (3th ed.). New Jersey: Prentice Hall Inc.
Puris, A., Bello, R., Trujillo, Y., Nowe, A., y Martínez, Y. (2007). Two-stage ACO to solve the job shop scheduling problem. Lecture and Notes in Computer Science.
Ramezanian, R., Aryanezhad, M. B., y Heydar, M. (2010). A Mathematical Programming Model for Flow Shop Scheduling Problems for Considering Just in Time Production. International Journal of Industrial Engineering & Production Research, 21(2), 97-104.
Ribas, I., Companys, R., y Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74, 41-54.
Ruiz, R., Sivrikaya, F., y Urlings, T. (2008). Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, 35, 1151 – 1175.
Sawik, T. (2007). A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing. European Journal of Operational Research, 180, 1060-1075.
Šeda, M. (2007). Mathematical Models of Flow Shop and Job Shop Scheduling Problems. World Academy of Science, Engineering and Technology, 1(31), 122-127.
Seido Naganoa, M., Almeida da Silva, A., y Nogueira Lorena, L. A. (2012). A new evolutionary clustering search for a no-wait flow shop problem with set-up times. Engineering Applications of Artificial Intelligence, 25, 1114–1120. doi: DOI: 10.1016
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Toro, M., Restrepo, G., y Granada, M. (2006). Adaptación de la técnica de Particle Swarm al problema de secuenciación de tareas. Scientia et Technica UTP, XII(32), 307-313.
Wang, J., Ersoy, O. K., He, M., y Wang, F. (2016). Multi-offspring genetic algorithm and its application to the traveling salesman problem. Applied Soft Computing, 43, 415-423.
Yamada, T. (2003). Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems. (Tesis Doctoral), Kyoto University, Kyoto, Japan.
Zhang, Y., Li, X., y Wang, Q. (2009). Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization. European Journal of Operational Research, 196, 869-876.

Downloads

Published

2017-12-18

How to Cite

Najarro, R., López, R., Racines, R. E., & Puris, A. (2017). An Hybrid Genetic Algorithm to Optimization of Flow Shop Scheduling Problems under Real Environments Constraints. Enfoque UTE, 8(5), pp. 14 – 25. https://doi.org/10.29019/enfoqueute.v8n5.176

Issue

Vol. 8 No. 5 (2017)

Section

Miscellaneous

License

The articles and research published by the UTE University are carried out under the Open Access regime in electronic format.  This means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the author. This is in accordance with the BOAI definition of open access. By submitting an article to any of the scientific journals of the UTE University, the author or authors accept these conditions.

The UTE applies the Creative Commons Attribution (CC-BY) license to articles in its scientific journals. Under this open access license, as an author you agree that anyone may reuse your article in whole or in part for any purpose, free of charge, including commercial purposes. Anyone can copy, distribute or reuse the content as long as the author and original source are correctly cited. This facilitates freedom of reuse and also ensures that content can be extracted without barriers for research needs.

 

This work is licensed under a Creative Commons Attribution 3.0 International (CC BY 3.0).

 

The Enfoque UTE journal guarantees and declares that authors always retain all copyrights and full publishing rights without restrictions [© The Author(s)]. Acknowledgment (BY): Any exploitation of the work is allowed, including a commercial purpose, as well as the creation of derivative works, the distribution of which is also allowed without any restriction.