Optimización del makespan en el problema de Job Shop Flexible con restricciones de transporte usando Algoritmos Genéticos

DOI: https://doi.org/10.31908/19098367.3820
Palabras clave: Algoritmo genético, AG, Job Shop, Job Shop Flexible, Job Shop Flexible Restricciones de transporte, Metaheurísticas, Makespan, Restricciones de transporte

Resumen

En el presente artículo se aborda el problema Flexible Job Shop Scheduling (FJSSP) con restricciones de transporte, con el objetivo de minimizar el makespan realizando la secuenciación y asignación de máquinas. Se llevó a cabo una revisión bibliográfica para orientar la metodología a utilizar, y a partir de allí, se decidió abordar el problema con un algoritmo genético, validando su efectividad a través de la comparación de los resultados obtenidos con distintas instancias propuestas en la literatura. Los resultados obtenidos muestran que el algoritmo genético propuesto es eficiente en las diferentes configuraciones del Job Shop clásico probadas, y para el Job Shop flexible con restricciones de transportes se presentan soluciones muy aproximadas a las mejores encontradas hasta el día de hoy. 

Descargas

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

Biografía del autor

Tatiana Andrea Castillo Jaimes, Universidad Industrial de Santander

Nació en Bucaramanga, Colombia. Se graduó en la Universidad Industrial de Santander como Ingeniera Industrial y Magister en Ingeniería Industrial. Ejerció profesionalmente en la Comercializadora Arte Laser de Bucaramanga y como docente en la Universidad Industrial de Santander y Universidad de Investigación y Desarrollo. Es investigadora afiliada al Grupo de Investigación en Optimización y Organización de Sistemas Productivos y Logísticos, OPALO. Entre sus campos de interés están la optimización de la cadena de suministros, los modelos de optimización y los algoritmos heurísticos y metaheurísticos.

Carlos Eduardo Díaz Bohórquez, Universidad Industrial de Santander

Nació en Socorro, Colombia. Se graduó como Ingeniero Industrial y Especialista en Evaluación y Gerencia de Proyectos en la Universidad Industrial de Santander. Además, obtuvo el título de Magister en Ingeniera Industrial en la Universidad de los Andes. Ha ejercido como docente en la Universidad de los Andes, la Universidad Pontificia Bolivariana Seccional Bucaramanga, la Universidad Cooperativa de Colombia y, actualmente en, la Universidad Industrial de Santander donde se desempeña como docente investigador del Grupo de Investigación en Optimización y Organización de Sistemas Productivos y Logísticos, OPALO. Entre sus campos de interés están la optimización de la programación de la producción, los modelos matemáticos y los algoritmos heurísticos y metaheurísticos.

Juan David Gómez Moreno, Avianca

nació en Bucaramanga, Colombia. Se graduó como Ingeniero Industrial en la Universidad Industrial de Santander. Se desempeñó como estudiante investigador en el Grupo de Investigación en Optimización y Organización de Sistemas Productivos y Logísticos, OPALO. Además, trabajó como Analista de Contratos en Oxy Colombia y posteriormente como Comprador Sr de Quala Colombia. Hoy día ejerce como Coordinador de Dotación Corporativa en Avianca, Colombia.

Edwin Alfredo Orduz Gonzáles, IBM

Nació en Bucaramanga, Colombia. Se graduó como Ingeniero Industrial en la Universidad Industrial de Santander. Se desempeñó como estudiante investigador en el Grupo de Investigación en Optimización y Organización de Sistemas Productivos y Logísticos, OPALO. Laborando para IBM Colombia como Sales & Staff Professional y Sales Specialist.

Myriam Leonor Niño Lopez, Universidad Industrial de Santander

nació en Bucaramanga, Colombia. Se graduó como Ingeniera Industrial y especialista en Gerencia de la Producción en Mejoramiento Continuo en la Universidad Industrial de Santander. También obtuvo el título de Magister en Administración en el Instituto Tecnológico y de Estudios Superiores de Monterrey, y el Doctorado en Dirección y Organización de Empresas en la Universidad Politécnica de Cataluña. Ejerció profesionalmente en la Universidad Industrial de Santander como Profesional Administrativo. Actualmente se desempeña como docente investigadora adscrita al Grupo de Investigación en Optimización y Organización de Sistemas Productivos y Logísticos, OPALO, en la Universidad Industrial de Santander. Entre sus campos de interés están la Ingeniería de Producción y la Gestión de las organizaciones.

Citas

hang, G., Shao, X., Li, P. and Gao, L., “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computers & Industrial Engineering, vol. 56, no. 4, pp. 1309-1318, 2009. doi: 10.1016/j.cie.2008.07.021

Tang, J., Zhang, G., Lin, B. and Zhang, B., “A hybrid algorithm for flexible job-shop scheduling problem”, Procedia Engineering, vol. 15, pp. 3678-3683, 2011. doi: 10.1016/j.proeng.2011.08.689

Fernández, M. A., “Soluciones metaheurísticas al ‘Job-shop scheduling problem with sequence-dependent setup times’”, Ph.D. dissertation, directed by M. del C. Rodríguez Vela, Universidad de Oviedo, España, Jul. 2011

Rossi, A., “Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships”, International Journal of Production Economics, vol. 153, pp. 253-267, 2014. doi: 0.1016/j.ijpe.2014.03.006

Garey, M. R. y D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, San Francisco, LA: Freeman, 1979.

John Henry Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, Cambridge, MA: MIT press, 1992.

Jain, A. S. and S. Meeran, “Deterministic job-shop scheduling: Past, present and future”, European journal of operational research, vol. 113, no. 2, pp. 390-434, 1999. doi: 10.1016/S0377-2217(98)00113-1

Graham, R. L., Lawler, E. L., Lenstra, J. K. and Kan, A. R., “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of discrete mathematics, vol. 5, pp. 287-326, 1979. doi: 10.1016/S0167-5060(08)70356-X

Conway, R. W., Maxwell, W. L. and Miller, L. W., Theory of scheduling. Courier Corporation, 2012.

Johnson, S. M., “Optimal two and three stage production schedules with setup times included”, Naval research logistics quarterly, vol. 1, no. 1, pp. 61-68, 1954. doi: 10.1002/nav.3800010110

Najid, N. M., Dauzere-Pérès, S. y Zaidat, A., “A modified simulated annealing method for flexible job shop scheduling problem”, IEEE International Conference on Systems, Man and Cybernetics, vol. 5, p. 6, 2002. doi: 10.1109/ICSMC.2002.1176334

Brucker, P. and Schlie, R., “Job-shop scheduling with multi-purpose machines”, Computing, vol. 45, no. 4, pp. 369-375, 1990.

Jansen, k., Mastrolilli, M. and Solis-Oba, R., “Approximation algorithms for flexible job shop problems” In: LATIN 2000: Theoretical Informatics. Springer Berlin Heidelberg, pp. 68-77, 2000.

A. P. Jiménez, C. A. Muñoz and E. M. Toro. “Solución del Problema de Flow Shop Flexible Aplicando el Algoritmo Genético de Chu- Beasley”, Entre Ciencia e Ingeniería, vol. 7, no. 13, pp. 34-40, 2013.

Xia, W. and Wu, Z., “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems”, Computers & Industrial Engineering, vol. 48, no. 2, pp. 409-425, 2005. doi: 10.1016/j.cie.2005.01.018

Osorio, J. C., Motoa, T. G., “Planificación jerárquica de la producción en un job shop flexible”, Revista Facultad de Ingeniería Universidad de Antioquia, no. 44, pp. 158-171, 2008.

Gao, J., Gen, M. and Sun, L., “Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm”, Journal of Intelligent Manufacturing, vol. 17, no. 4, pp. 493-507, 2006. doi: 10.1007/s10845-005-0021-x

Zhang, G., Shao, X., Li, P. and Gao, L., “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem”, Computers & Industrial Engineering, vol. 56, no. 4, pp. 1309-1318, 2009. doi: 10.1016/j.cie.2008.07.021

De Giovanni, L. and Pezzella, F., “An improved genetic algorithm for the distributed and flexible job-shop scheduling problem”, European journal of operational research, vol. 200, no. 2, pp. 395-408, 2010. doi: 10.1016/j.ejor.2009.01.008

Zhang, Q., Manier, H. and Manier, M. A., “A genetic algorithm with Tabu Search procedure for flexible Job Shop Scheduling with transportation constraints and bounded processing times”, Computers & Operations Research, vol. 39, no. 7, pp. 1713-1723, 2012. doi: 10.1016/j.cor.2011.10.007

Moslehi, G. and Mahnam, M., “A Pareto approach to multi-objective flexible Job-Shop Scheduling problem using Particle Swarm Optimization and local search”, International Journal of Production Economics, vol. 129, no. 1, pp. 14-22, 2011. doi: 10.1016/j.ijpe.2010.08.004

González, M. A., Rodríguez Vela, C. and Varela, R., “An efficient memetic algorithm for the flexible job shop with setup times”, In: Twenty-Third International Conference on Automated Planning and Scheduling, Febrero, 2013.

Liu, Z., Ma, S., Shi, Y. and Teng, H., “Solving multi-objective Flexible Job Shop Scheduling with transportation constraints using a micro artificial bee colony algorithm”, In: Computer Supported Cooperative Work in Design (CSCWD), 2013 IEEE 17th International Conference on, IEEE, pp. 427-432, Junio, 2013. doi: 10.1109/CSCWD.2013.6581001

Rossi, A., “Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships” International Journal of Production Economics, vol. 153, pp. 253-267, 2014. doi: 10.1016/j.ijpe.2014.03.006

Gallego, G., “Linear control policies for scheduling a single facility after an initial disruption”, Informe técnico No. 770, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, enero, 1988.

DE JONG, K. A., “An analysis of the behaviour of a class of genetic adaptive systems”. Tesis doctoral, Universidad de Michigan, Ann Arbor, MI, USA, 1975.

Fisher, H. and Thompson, G. L., “Probabilistic learning combinations of local job-shop scheduling rules”, Industrial scheduling, vol. 3, pp. 225-251, 1963.

Lawrence, S., “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement)”. Tesis doctoral, Carnegie-Mellon University, Graduate School of Industrial Administration, Pittsburgh, PA, 1984.

Fattahi, P., Mehrabad, M. Saidi, J. y Fariborz., “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems”, Journal of Intelligent Manufacturing, vol. 18, no 3, pp. 331-342, 2007. doi: 10.1007/s10845-007-0026-8

Dauzère-Pérès, S. and Paulli, J., “An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search”, Annals of Operations Research, vol. 70, p. 281-306, 1997. doi: 10.1023/A:1018930406487

Hurink, J. and Knust, S., “Makespan minimization for flow-shop problems with transportation times and a single robot”, Discrete Applied Mathematics, vol. 112, no 1, pp. 199-216, 2001. doi: 10.1016/S0166-218X(00)00316-4

Deroussi, L. and Norre, S., Simultaneous scheduling of machines and vehicles for the flexible job shop problem. En: International conference on metaheuristics and nature inspired computing. 2010.

Zhang, Q., Manier, H. and Manier, M.-A., “A genetic algorithm with Tabu Search procedure for flexible job shop scheduling with transportation constraints and bounded processing times”, Computers & Operations Research, vol. 39, no 7, p. 1713-1723, 2012. doi: 10.1016/j.cor.2011.10.007

Box, G. E. P., Stuart Hunter, J. and Hunter, W. G., Statistics for Experimenters: Design, Innovation, and Discovery. Wiley-Interscience: New York, NY, USA, vol. 2, 2005.

Castrillón, O. D., Giraldo J. A. y Sarache, W. A., “Solución de un problema Job Shop con un agente inteligente”, Ingeniería y Ciencia, vol. 5, no. 10, pp. 75–92, 2009.

Publicado
2018-12-12
Cómo citar
Castillo Jaimes, T., Díaz Bohórquez, C., Gómez Moreno, J., Orduz Gonzáles, E., & Niño Lopez, M. (2018). Optimización del makespan en el problema de Job Shop Flexible con restricciones de transporte usando Algoritmos Genéticos. Entre Ciencia E Ingeniería, 12(24), 105-115. https://doi.org/10.31908/19098367.3820
Número
Vol. 12 Núm. 24 (2018)
Sección
Artículos
Derechos de autor 2019 Entre Ciencia e Ingeniería