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

T. A. Castillo, C. E. Díaz B., J. D. Gómez, E. A. Orduz, M. L. Niño

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 fl exible con restricciones de transportes se presentan soluciones muy aproximadas a las mejores encontradas hasta el día de hoy.


Palabras clave


Algoritmo genético; AG; Job Shop; Job Shop Flexible; Job Shop Flexible Restricciones de transporte; Metaheurísticas; Makespan; Restricciones de transporte.

Texto completo:

PDF

Referencias


  • 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
  • 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.




DOI: http://dx.doi.org/10.31908/19098367.3820

Enlaces refback

  • No hay ningún enlace refback.


Copyright (c) 2018 Entre ciencia e ingeniería

Licencia Creative Commons
Este trabajo está licenciado bajo una Licencia Internacional Creative Commons Atribución-NoComercial 4.0.