Un Algoritmo Genético Híbrido para la Optimización del Flow Shop Scheduling bajo Restricciones de Entornos Reales

Autores/as

  • 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

Palabras clave:

algoritmo genético híbrido, secuenciación de tareas, programación de la producción, búsqueda local de vecindad variable

Resumen

Este trabajo tiene como objetivo analizar el efecto de la inclusión de varias restricciones que influyen negativamente en la programación de la producción en un ambiente de manufactura real. Para la solución del problema de secuenciación tratado en esta investigación, conocido como Flow Shop Scheduling, se introduce un eficiente Algoritmo Genético combinado con una Búsqueda Local de Vecindad Variable para problemas de n tareas y m máquinas minimizando el tiempo de completamiento total de las tareas o makespan. Las restricciones de fechas de liberación, tiempos de configuración dependientes de la secuencia y tiempos de transportación son introducidas. Estas son restricciones comunes que pueden ser encontradas en múltiples ambientes manufactureros donde existen máquinas y herramientas, y un conjunto de tareas debe procesarse en estas siguiendo el mismo patrón de flujo. Los experimentos computacionales realizados sobre un conjunto de instancias de problemas de diferentes tamaños de complejidad demuestran que la metaheurística híbrida propuesta alcanza soluciones de alta calidad comparables con los óptimos reportados.

Metrics

Descargas

La descarga de datos todavía no está disponible.

Citas

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.

Publicado

2017-12-18

Cómo citar

Najarro, R., López, R., Racines, R. E., & Puris, A. (2017). Un Algoritmo Genético Híbrido para la Optimización del Flow Shop Scheduling bajo Restricciones de Entornos Reales. Enfoque UTE, 8(5), pp. 14 - 25. https://doi.org/10.29019/enfoqueute.v8n5.176

Número

Vol. 8 Núm. 5 (2017)

Sección

Misceláneos

Los artículos e investigaciones publicadas por la Universidad UTE, se realizan en régimen de Acceso Abierto [Open Access] en formato electrónico. Al enviar un artículo a cualquiera de las revistas científicas de la Universidad UTE, el o los autores aceptan estas condiciones.

La UTE aplica la licencia Creative Commons Attribution (CC-BY) a los artículos de sus revistas científicas. En virtud de esta licencia de acceso abierto, como autor usted acuerda que cualquier persona puede reutilizar su artículo en su totalidad o en parte para cualquier propósito, de forma gratuita, incluso para fines comerciales. Cualquiera puede copiar, distribuir o reutilizar el contenido siempre y cuando el autor y la fuente original estén correctamente citados. Esto facilita la libertad de reutilización y también asegura que el contenido pueda ser extraído sin barreras para necesidades de investigación.

 

Esta obra está bajo una Creative Commons Attribution 3.0 International (CC BY 3.0).

 

Además, la Revista Enfoque UTE garantiza y declara que los autores conservan siempre todos los derechos de autor y de publicación de sus obras originales sin restricciones [© Los Autores].  El reconocimiento (BY) permite cualquier explotación de la obra, incluyendo una finalidad comercial, así como la creación de obras derivadas, la distribución de las cuales también está permitida sin ninguna restricción.