Modelos matemáticos para programação de job shop com tempos de setup independentes da sequência
DOI:
https://doi.org/10.14488/1676-1901.v17i1.2504Palavras-chave:
Programação da produção. Job shop. Setup independente. Programação linear inteira mista.Resumo
Este trabalho aborda o problema de programação da produção em job shop com tempos de setup explícitos e independentes da sequência de processamento das tarefas visando minimizar a duração total da programação (makespan). Na conhecida notação de três campos, este problema é representado por Jm|sjk|Cmax. O ambiente job shop é aquele em que há um conjunto de máquinas ou recursos diferentes que devem processar um conjunto de tarefas, sendo que cada tarefa possui uma rota específica e pré-determinada para processamento nas máquinas. Para problemas com duas máquinas, nesta pesquisa propõe-se uma adaptação no clássico Algoritmo de Jackson, que fornece a solução ótima para o caso com setup incluído nos tempos de processamento das tarefas. E para problemas genéricos com m máquinas, foram elaborados e implementados dois modelos matemáticos de programação linear inteira mista para os casos de setup antecipado (aquele que pode ser iniciado antes da liberação da tarefa) e não antecipado, que fornecem soluções em tempo computacional viável para problemas-testes com até 20 tarefas e 7 máquinas.
Downloads
Referências
ADAMS, J.; BALAS, E.; ZAWACK, D. The shifting bottleneck procedure for job shop scheduling. Management Science, v. 34, p. 391-401, 1988. http://dx.doi.org/10.1287/mnsc.34.3.391
ALDAKHILALLAH, K.A.; RAMESH, R. Cyclic scheduling heuristic for a re-entrant job shop manufacturing environment. International Journal of Production Research, v. 39, p. 2635-2657, 2001. http://dx.doi.org/10.1080/00207540110047711
ALLAHVERDI, A. Third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, v. 246, n. 2, p. 345-378, 2015. http://dx.doi.org/10.1016/j.ejor.2015.04.004
ALLAHVERDI, A.; CHENG, T. C. E.; KOVALYOV, M. Y. A survey of scheduling problems with setups times or costs. European Journal of Operational Research, v. 187, n. 3, p. 985-1032, 2008. http://dx.doi.org/10.1016/j.ejor.2006.06.060
ALLAHVERDI, A.; GUPTA, J.N.D.; ALDOWAISAN, T. A review of scheduling research involving setup considerations. Omega – International Journal of Management Science, v. 27, p. 219-239, 1999. http://dx.doi.org/10.1016/S0305-0483(98)00042-5
ALLAHVERDI, A.; SOROUSH, H. M. The significance of reducing setup times/setup costs. European Journal of Operational Research, v. 187, n. 3, p. 978-984, 2008. http://dx.doi.org/10.1016/j.ejor.2006.09.010
AL-SALEM, A. A heuristic to minimize makespan in proportional parallel flow shops. International Journal of Computing & Information Sciences, v. 2, p. 98-107, 2004. http://www.ijcis.info/Vol2N2/98-107OKS.pdf
BLAZEWICZ, J.; DOMSCHKE, W., PESCH, E. The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, v. 93, p. 1-33, 1996.
http://dx.doi.org/10.1016/0377-2217(95)00362-2
CHAN, F. T. S.; CHOY K.L.; BIBHUSHAN. A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Systems with Applications, v. 38, p. 8703-8715, 2011. http://dx.doi.org/10.1016/j.eswa.2011.01.078
CHIN, Y.L. Job shop scheduling heuristics for sequence dependent setup. Computers & Industrial Engineering, v. 29, p. 279-283, 1995. http://dx.doi.org/10.1016/0360-8352(95)00085-F
FREITAS, F.F.T.; VIEIRA, G.E. Tendências de aplicações da otimização por colônia de formigas na programação de job-shops. Revista Produção Online, v. 10, n. 1, p. 95-123, 2010. http://dx.doi.org/10.14488/1676-1901.v10i1.441
FUCHIGAMI, H. Y. Sequenciamento da produção em sistemas flow shop. UFG, Goiânia – GO, 2015.
JACKSON, J. R. An extension of Johnson’s results on job lot scheduling. Naval Research Logistics Quarterly, v. 3, p. 201-203, 1956. http://dx.doi.org/10.1002/nav.3800030307
JEONG, H.; PARK, J. LEACHMAN, R.C. A batch splitting method for a job shop scheduling problem in an MRP environment. International Journal of Production Research, v. 37, p. 3583-3598, 1999. http://dx.doi.org/10.1080/002075499190194
JOHNSON, S. M. Optimal two- and three- stage production schedules with setup times included. Naval Research Logistic Quarterly, v. 1, p. 61-68, 1954. http://dx.doi.org/10.1002/nav.3800010110
LOW, C.; HSU, C.-M., HUANG, K.-I. Benefits of lot splitting in job-shop scheduling. International Journal of Advanced Manufacturing Technology, v. 24, p. 773-780, 2004. http://dx.doi.org/10.1007/s00170-003-1785-9
MÜLLER, G. I.; GÓMEZ, A. T. Um estudo do comportamento dos tempos de makespan, atraso e setup no problema de escalonamento de job shop. Hifen, v. 31, n. 59-60, p. 148-154, 2007.
PACHECO, R.F.; SANTORO, M.C. Proposta de classificação hierarquizada dos modelos de solução para o problema de job shop scheduling. Gestão & Produção, v. 6, n. 1, p. 1-15, 1999. http://dx.doi.org/10.1590/S0104-530X1999000100001
PARVEEN, S.; ULLAH, H. Review on job-shop and flow-shop scheduling using multi criteria decision making. Journal of Mechanical Engineering, v. 41, n. 2, p. 130-146, 2010.
PINEDO, M. Scheduling: theory, algorithms, and systems. 5. ed. New Jersey: Prentice-Hall, 2015.
RAHIME, S.E.; ARSLAN, O. Simulation analysis of lot streaming in job shops with transportation queue disciplines. Simulation Modelling Practice and Theory, v. 17, p. 442-453, 2009.
http://dx.doi.org/10.1016/j.simpat.2008.10.002
SONG, H.; YI, S.; SHEN, H. A study of job shop standard setup time quota. Production Management, v. 10, n. 2, p. 185-196, 2016. http://dx.doi.org/10.1007/s11740-015-0649-0
SOTSKOV, Y.N.; TAUTENHAHN, T.; WERNER, F. On the application of insertion techniques for job shop problems with setup times. RAIRO – Operations Research, v. 33, n. 2, p. 209-245, 2010. http://dx.doi.org/10.1051/ro:1999110
TARANTILIS, C. D.; KIRANOUDIS, C. T. A list-based threshold accepting method for job shop scheduling problems. International Journal of Production Economics, v. 77, p. 159–171, 2002. http://dx.doi.org/10.1016/S0925-5273(01)00231-6
WILBRECHT, J.K.; PRESCOTT, W.B. The influence of setup time on job shop performance. Management Science, v. 16, p. B274-B280, 1969. http://dx.doi.org/10.1287/mnsc.16.4.B274
Publicado
Como Citar
Edição
Seção
Licença
A Revista se reserva no direito de efetuar, no artigo publicado, alterações de ordem normativa, ortográfica e gramatical, com vistas a manter o padrão culto da língua, respeitando, porém, o estilo dos autores.
A obra publicada é de inteira responsabilidade do(s) autor(es), cabendo à Revista Produção Online apenas a avaliação da obra, na qualidade de veículo de publicação científica. A Revista Produção Online não se responsabiliza por eventuais violações à Lei nº 9.610/1998, Lei de Direito Autoral.
A revista Produção Online permite que o autor detenha o copyright dos artigos aceitos para publicação, sem restrições.
Esta obra está licenciada sob uma Licença Creative Commons.
