O uso do Mixed-Integer e Constraint Programming para a resolução do Job Shop Scheduling Problem

• Neuenfeldt Júnior, Alvaro ^[1]
  1. [1] Universidade Federal de Santa Maria

     Universidade Federal de Santa Maria

     Brasil

     
• Localización: Dirección y organización: Revista de dirección, organización y administración de empresas, ISSN 1132-175X, Nº. 69, 2019, págs. 27-35
• Idioma: español
• DOI: 10.37610/dyo.v0i69.559
• Enlaces
  • Texto Completo Ejemplar
• Resumen

  • Independente do processo industrial, o estudo sobre a alocação de recursos produtivos é atualmente um dos temas mais abordados cientificamente, principalmente quando envolve a busca pela gestão de forma mais eficiente e dinâmica às exigências do mercado ao qual a empresa está inserida. Para tanto, o presente artigo tem por objetivo comparar o desempenho de três técnicas de otimização ao contexto do Job Shop Scheduling Problem (JSSP), sendo uma baseada em modelagens Mixed-Integer Programming (MIP) e outras duas resolvidas com base nos conceitos do Constraint Programming (CP), por meio da utilização de 82 instâncias disponibilizadas pela biblioteca digital OR Library. Como resultados, foi possível verificar que a versão padrão do CP disponibilizado pelo software CPLEX Optimization Studio é o mais eficiente para encontrar soluções ótimas, conforme benchmark realizado com estudos anteriormente publicados cientificamente.

• Referencias bibliográficas
  • Aggoune, R. (2004). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational...
  • Andrés, C., e Maheut, J. (2018). Secuenciación con Almacenes Limitados. Una Revisión de la Literatura. Dirección y Organización, 66, 17-33.
  • Araúzo, J. A., del Olmo, R., e Laviós, J. J. (2013). Subasta combinatoria para la programación dinámica en sistemas de fabricación distribuidos....
  • Applegate, D., e Cook, W. (1991). A computational study of the job-shop scheduling problem. Orsa Journal on Computing, 3(2), 149-156.
  • Bautista, J., e Alfaro, R. (2018). Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types. Central...
  • Chaudhry, I. A., & Khan, A. A. (2016). A research survey: review of flexible job shop scheduling techniques. International Transactions...
  • Çaliş, B., & Bulkan, S. (2015). A research survey: review of AI solution strategies of job shop scheduling problem. Journal of Intelligent...
  • Eroglu, D. Y., e Ozmutlu, H. C. (2014). Mip models and hybrid algorithms for simultaneous job splitting and scheduling on unrelated parallel...
  • Gao, L., Zhang, G., Zhang, L., e Li, X. (2011). An efficient memetic algorithm for solving the job shop scheduling problem. Computers &...
  • Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1),...
  • Kashan, A. H., Karimi, B., e Jolai, F. (2010). An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single...
  • Klemmt, A., Horn, S., Weigert, G., e Wolter, K-J. (2009). Simulation-based optimization vs. mathematical programming: A hybrid approach for...
  • Ku, W-Y., e Beck, J. C. (2014). Revisiting off-the-shelf mixed integer programming and constraint programming models for job shop scheduling....
  • Ku, W. Y., & Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations...
  • Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8(2), 219-223.
  • Martin, P., e Shmoys, D. B. (1996). A new approach to computing optimal schedules for the job-shop scheduling problem. Pages 389-403 of: Integer...
  • Mateo, M. R. I., e Pascual, R. C. (2009). Un procedimiento GRASP para la programación de pedidos en máquinas paralelas con tiempos de preparación....
  • Naderi, B., Zandieh, M., e Fatemi Ghomi, S. M. T. (2009). Scheduling job shop problems with sequence dependent setup times. International...
  • Neuenfeldt Júnior, A., Silva, E., Gomes, A. M., Soares, C., e Oliveira, J. F. (2019). Data mining based framework to assess solution quality...
  • Pezzella, F., Morganti, G., e Ciaschetti, G. (2008). A genetic algorithm for the exible job-shop scheduling problem. Computers & Operations...
  • Rossit, D. A., Tohmé, F., & Frutos, M. (2018). The non-permutation flow-shop scheduling problem: a literature review. Omega, 77, 143-153.
  • Runarsson, T. P., Schoenauer, M., e Sebag, M. (2012). Pilot, rollout and monte carlo tree search methods for job shop scheduling. Pages 160-174...
  • Sharma, P., & Jain, A. (2016). A review on job shop scheduling with setup times. Proceedings of the Institution of Mechanical Engineers,...
  • Vaessens, R. J. M., Aarts, E. H. L., e Lenstra, J. K. (1996). Job shop scheduling by local search. Journal on Computing, 8(3), 302-317.
  • Yilmaz, E., Duygu, O., Cenk, H., e Ozmutlu, S. (2014). Genetic algorithm with local search for the unrelated parallel machine scheduling problem...
  • Zhang, J., Ding, G., Zou, Y., Qin, S., & Fu, J. (2019). Review of job shop scheduling research and its new perspectives under Industry...