Um estudo computacional de novas regras de prioridade para flow shop com tempos de setup e diferentes datas de liberação

Caio Soares de Araújo, Helio Yochihiro Fuchigami

Resumo


Este trabalho aborda o sistema de produção flow shop com tempos de setup independentes da sequência, tarefas com diferentes instantes de liberação e dois problemas distintos: minimização da duração total da programação (makespan) e do tempo médio de fluxo (flowtime). Foi empreendido um amplo estudo computacional do desempenho de novas regras de prioridade, muito utilizadas na prática pelas empresas, aqui definidas com base na estrutura dos problemas analisados. Conforme é bem conhecido, a eficiência computacional das regras de prioridade como métodos de solução já é presumida. Portanto, nesta pesquisa focou-se na análise da eficácia, ou seja, da qualidade da solução atingida pela aplicação de tais regras nos dois problemas considerados. Os resultados provaram a aplicabilidade dos métodos propostos e identificaram as melhores regras para cada caso, com seus respectivos critérios de ordenação.

Palavras-chave


Programação da produção. Flow shop. Regras de prioridade. Setup independente. Datas de liberação.

Texto completo:

PDF ♪ÁUDIO♪

Referências


ABEDI, M.; SEIDGAR, H.; FAZLOLLAHTABAR, H.; BIJANI, R. Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits. International Journal of Production Research, v. 53, n. 6, p. 1680-1711, 2015. http://dx.doi.org/10.1080/00207543.2014.952795

ALLAHVERDI, A. The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, v. 246, n. 2, p. 345-378, 2015. https://doi.org/10.1016/j.ejor.2015.04.004

ALLAHVERDI, A.; GUPTA, J.N.D.; ALDOWAISAN, T. A review of scheduling research involving setup considerations. Omega – The International Journal of Management Science, v. 27, p. 219-239, 1999.

https://doi.org/10.1016/S0305-0483(98)00042-5

ALLAHVERDI, A.; NG, C.T.; CHENG, T.C.E.; KOVALYOV, M.Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, v. 187, p. 985-1032, 2008. https://doi.org/10.1016/j.ejor.2006.06.060

AMIRIAN, H.; SAHRAEIAN, R. A hybrid differential evolution for general multi-objective flow shop problem with a modified learning effect. Journal of Engineering Manufacturing, v. 230, n. 12, p. 2275-2285, 2016. http://dx.doi.org/10.1177/0954405416673094

BAI, D. Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates. International Journal of Systems Science, v. 46, n. 11, p. 1994-2005, 2015. http://dx.doi.org/10.1080/00207721.2013.843736

BAI, D.; HUO, M.; TANG, L. A new lower bound for flow shop makespan with release dates. IEEE, p. 276-280, 2008. https://doi.org/10.1109/SOLI.2008.4686405

BAKER, K.R.; TRIETSCH, D. Principles of sequencing and scheduling. New Jersey: John Wiley & Sons, 2009.

BALASUNDARAM, R.; BASKAR, N.; SANKAR, R.S. A new approach to generate dispatching rules for two machine flow shop scheduling using data mining. Procedia Engineering, v. 38, p. 238-245, 2012.

https://doi.org/10.1016/j.proeng.2012.06.031

BARMAN, S. The impact of priority rule combinations on lateness and tardiness. IIE Transactions, v. 30, n. 5, p. 495-504, 1998. https://doi.org/10.1023/A:1007503508080

BIANCO, L.; DELL’OLMO, P.; GIORDANI, S. Flow shop no-wait scheduling with sequence dependent setup times and release dates. INFOR, v. 37, n. 9, p. 3-19, 1999. http://dx.doi.org/10.1080/03155986.1999.11732365

BLACKSTONE, J.H.; PHILLIPS, D.T.; HOGG, G.L. A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, v. 20, n. 1, p. 27-45, 1982. http://dx.doi.org/10.1080/00207548208947745

BRAH, S.A; WHEELER, G.E. Comparison of scheduling rules in a flow shop with multiple processors: a simulation. Simulation, v. 71, n. 5, p. 302-311, 1998. http://journals.sagepub.com/doi/abs/10.1177/003754979807100501

BÜLBÜL, K.; KAMINSKY, P.; YANO, C. Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs. Naval Research Logistics, v. 51, p. 407-445, 2004. http://dx.doi.org/10.1002/nav.20000

CHEN, H.; ZHOU, S.; LI, X.; XU, R. A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking. International Journal of Production Research, v. 52, n. 19, p. 5714-5734, 2014. http://dx.doi.org/10.1080/00207543.2014.910625

CHENG, J.; STEINER, G.; STEPHENSON, P. A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times. European Journal of Operational Research, v. 130, p. 559-575, 2001. https://doi.org/10.1016/S0377-2217(99)00415-4

CHENG, T.C.E.; GUPTA, J.N.D.; WANG, G. A review of flowshop scheduling research with setup times. Production and Operations Management, v. 9, n. 3, p. 262-282, 2000. https://doi.org/10.1111/j.1937-5956.2000.tb00137.x

CHIANG, T.C.; FU, L.C. Using dispatching rules for job shop scheduling with due date-based objectives. International Journal of Production Research, v. 45, n. 14, p. 3245-3262, 2007. https://doi.org/10.1109/ROBOT.2006.1641909

CHIHAOUI, F.B.; KACEM, I.; HADJ-ALOUANE, A.B.; DRIDI, N.; REZG, N. No-wait scheduling of a two-machine flow-shop to minimize the makespan under non availability constraints and different release dates. International Journal of Production Research, v. 49, n. 21, p. 6273-6286, 2011. http://dx.doi.org/10.1080/00207543.2010.531775

EL-BOURI, A. A cooperative dispatching approach for minimizing mean tardiness in a dynamic flowshop. Computers & Operations Research, v. 39, p. 1305-1314, 2012. https://doi.org/10.1016/j.cor.2011.07.004

EL-BOURI, A.; BALAKRISHNAN, S.; POPPLEWELL, N. Cooperative dispatching for minimizing mean flowtime in a dynamic flowshop. International Journal of Production Economics, v. 113, p. 819-833, 2008. https://doi.org/10.1016/j.ijpe.2007.11.005

FRAMINAN, J.M.; GUPTA, J.N.D.; LEISTEN, R. A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, v. 55, p. 1243-1255, 2004.

https://link.springer.com/article/10.1057/palgrave.jors.2601784

FRAMINAN, J.M.; LEISTEN, R.; RUIZ-USANO, R. Comparison of heuristics for flowtime minimization in permutation flowshops. Computers & Operations Research, v. 32, p. 1237-1254, 2005. https://doi.org/10.1016/j.cor.2003.11.002

FUCHIGAMI, H.Y. Proposição de algoritmo Simulated Annealing para programação em flow shops paralelos proporcionais com tempos de setup explícitos. Produção Online, v. 14, n. 3, p. 997-1023, 2014. http://dx.doi.org/10.14488/1676-1901.v14i3.1631

FUCHIGAMI, H.Y.; MOCCELLIN, J.V. Desempenho relativo de regras de prioridade para programação de flow shop híbrido com tempos de setup. Revista Produção Online, v. 15, n. 4, p. 1174-1194, 2015. http://dx.doi.org/10.14488/1676-1901.v15i4.1791

FUCHIGAMI, H.Y.; MOCCELLIN, J.V. Efeitos de regras de prioridade para programação da produção em sistemas industriais complexos. Produção Online, v. 16, n. 1, p. 3-25, 2016. http://dx.doi.org/10.14488/1676-1901.v16i1.1720

FUCHIGAMI, H.Y.; MOCCELLIN, J.V.; RUIZ, R. Novas regras de prioridade para programação em flexible flow line com tempos de setup explícitos. Production, v. 25, n. 4, p. 779-790, 2015. http://dx.doi.org/10.1590/0103-6513.089212

FRAMINAN, J.M.; PEREZ-GONZALEZ, P. Order scheduling with tardiness objective: improved approximate solutions. European Journal of Operational Research, in press, 2017. http://doi.org/10.1016/j.ejor.2017.10.064

GRABOWSKI, J.; SKUBALSKA, E.; SMUTNICKI, C. On flow shop scheduling with release and due dates to minimize maximum lateness. The Journal of the Operational Research Society, v. 34, n. 7, p. 615-620, 1983. http://www.jstor.org/stable/2581775

GRAHAM, R.L.; LAWLER, E.L.; LENSTRA, I.K.; RINNOOY KAN, A.H.G. Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, v. 5, p. 287-326, 1979. http://dx.doi.org/10.1016/S0167-5060(08)70356-X

GUPTA, J.N.D.; STAFFORD JR., E.F. Flowshop scheduling research after five decades. European Journal of Operational Research, v. 169, p. 699-711, 2006. https://doi.org/10.1016/j.ejor.2005.02.001

HALL, L. A polynomial approximation scheme for a constrained flow-shop scheduling problem. Mathematics of Operations Research, v. 19, n. 1, p. 68-85, 1994. https://doi.org/10.1287/moor.19.1.68

HALL, L.A. Approximability of flow shop scheduling. Mathematical Programming, v. 82, n. 1, p. 175-190, 1998. https://doi.org/10.1007/BF01585870

HAOUARI, M.; LADHARI, T. Minimizing maximum lateness in a flow shop subject to release dates. Journal of the Operational Research Society, v. 58, p. 62-72, 2007. http://dx.doi.org/10.1057/palgrave.jors.2602092

HAUPT, R. A survey of priority rule-based scheduling. OR Spektrum, v. 11, p. 3-16, 1989. https://doi.org/10.1007/BF01721162

JAYAMOHAN, M.; RAJENDRAN, C. New dispatching rules for shop scheduling: a step forward. International Journal of Production Research, 38:3, p. 563-586, 2000. http://dx.doi.org/10.1080/002075400189301

JÓZEFCZYK, J.; MARKOWSKI, M.; BALGABAEVA, L. Routing flow-shop with buffers and ready times – comparison of selected solution algorithms. Management and Production Engineering Review, v. 5, n. 4, p. 26-35, 2014. http://dx.doi.org/10.2478/mper-2014-0033

JUNG, C.F. Metodologia para pesquisa & desenvolvimento: aplicada a novas tecnologias, produtos e processos. Rio de Janeiro: Axcel Books, 2004.

KALCZYNSKI, P.J.; KAMBUROWSKI, J. An empirical analysis of heuristics for solving the two-machine flow shop problem with job release dates. Computers & Operations Research, v. 39, p. 2659-2665, 2012. https://doi.org/10.1016/j.cor.2012.01.011

KAMINSKY, P.; SIMCHI-LEVI, D. Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates. Operations Research Letters, v. 29, p. 141-148, 2001. http://dx.doi.org/10.1080/00207721.2013.843736

KASHYRSKIKH, K.N.; POTTS, C.N.; SEVASTIANOV, S.V. A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates. Discrete Applied Mathematics, v. 114, p. 255-271, 2001. https://doi.org/10.1016/S0166-218X(00)00374-7

KIANFAR, K.; FATEMI GHOMI, S.M.T.; KARIMI, B. New dispatching rules to minimize rejection and tardiness costs in a dynamic flexible flow shop. The International Journal of Advanced Manufacturing Technology, v. 45, p. 759-771, 2009. https://doi.org/10.1007/s00170-009-2015-x

KIANFAR, K.; FATEMI GHOMI, S.M.T.; OROOJLOOY JADID, A. Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA. Engineering Applications of Artificial Intelligence, v. 25, p. 494-506, 2012. https://doi.org/10.1016/j.engappai.2011.12.004

KORYTKOWSKI, P.; WISNIEWSKI, T.; RYMASZEWSKI, S. An evolutionary simulation-based optimization approach for dispatching scheduling. Simulation Modelling Practice and Theory, v. 35, p. 69-85, 2013. http://dx.doi.org/10.1080/00207540110064938

KURZ, M.E.; ASKIN, R.G. Heuristic scheduling of parallel machines with sequence-dependent set-up times. International Journal of Production Research, v. 39, n. 16, p. 3747-3769, 2001. http://dx.doi.org/10.1080/00207540110064938

LADHARI, T.; HAOUARI, M. A branch-and-bound algorithm for the permutation flow shop scheduling problem subject to release dates and delivery times. IEEE, p. 1-5, 2006. https://doi.org/10.1109/ICSSSM.2006.320673

LENSTRA, J.K.; RINNOOY KAN, A.H.G.; BRUCKER, P. Complexity of machine scheduling problems. Annals of Operations Research, v. 1, p. 343-362, 1977. https://doi.org/10.1016/S0167-5060(08)70743-X

LIU, H.; QUEYRANNE, M.; SIMCHI-LEVI, D. On the asymptotic optimality of algorithms for the flow shop problem with release dates. Naval Research Logistics, v. 52, p. 232-242, 2005. https://doi.org/10.1002/nav.20066

MA, T.; CHU, C.; ZUO, C. A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, v. 58, p. 199-211, 2010. https://doi.org/10.1016/j.cie.2009.04.014

MacCARTHY, B.L.; LIU, J. Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal of Production Research, v. 31, n. 1, p. 59-79, 1993. http://dx.doi.org/10.1080/00207549308956713

MARTINS, R.A. Abordagens Quantitativa e Qualitativa. In: MIGUEL, P.A.C.(Org.). Metodologia de pesquisa em Engenharia de Produção e Gestão de Operações. Rio de Janeiro: Elsevier, 2010. p. 45-61, cap. 3.

MUTHUSWAMY, S.; VÉLEZ-GALLEGO, M.; MAYA, J.; ROJAS-SANTIAGO, M. Minimizing makespan in a two-machine no-wait flow shop with batch processing machines. The International Journal of Advanced Manufacturing Technology, p. 1-10, 2012. http://dx.doi.org/10.1007/s00170-012-3906-9

NAKANO, D. Métodos de Pesquisa Adotados na Engenharia de Produção e Gestão de Operações. In: MIGUEL, P.A.C.(Org.). Metodologia de pesquisa em Engenharia de Produção e Gestão de Operações. Rio de Janeiro: Elsevier, 2010. p. 63-72, cap. 4.

PAN, Q.-K.; RUIZ, R. A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers & Operations Research, v. 40, p. 117-128, 2013.

https://doi.org/10.1016/j.cor.2012.05.018

PINEDO, M.L. Scheduling: theory, algorithms, and systems. New Jersey: Prentice-Hall, 5ªed., 2016.

POTTS, C.N.; STRUSEVICH, V.A. Fifty years of scheduling: a survey of milestones. Journal of the Operational Research Society, v. 60, p. S41-S68, 2009. http://www.jstor.org/stable/40206725

REN, T.; DIAO, Y.; LUO, X. Optimal results and numerical simulations for flow shop scheduling problem. Journal of Applied Mathematics, v. 2012, p. 1-9, 2012. http://dx.doi.org/10.1155/2012/395947

REN, T.; GUO, M.; LIN, L.; MIAO, Y. A local search algorithm for the flow shop scheduling problem with release dates. Discrete Dynamics in Nature and Society, v. 2015, p. 1-8, 2015. http://dx.doi.org/10.1155/2015/320140

REN, T.; ZHANG, C.; LIN, L.; GUO, M.; XIE, X. Asymptotic analysis of SPTA-based algorithm for no-wait flow shop scheduling problem with release dates. The Scientific World Journal, v. 2014, p. 1-7, 2014. http://dx.doi.org/10.1155/2014/979238

REZA HEJAZI, S.; SAGHAFIAN, S. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, v. 43, n. 14, p. 2895-2929, 2005. http://dx.doi.org/10.1080/0020754050056417

RUIZ, R.; MAROTO, C. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, v. 165, p. 479-494, 2005. https://doi.org/10.1016/j.ejor.2004.04.017

SUNG, C.S.; KIM, Y.H. Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed. Computers & Operations Research, v. 29, p. 275-294, 2002. https://doi.org/10.1016/S0305-0548(00)00071-X

T’KINDT, V.; BILLAUT, J.-C. Multicriteria scheduling: theory, models and algorithms. Berlin Heidelberg: Springer-Verlag, 2006. 2nd ed.

TA, Q.C.; BILLAUT, J.-C.; BOUQUARD, J.-L. Matheuristic algorithms for minimizing total tardiness in the m-machine flow shop scheduling problem. Journal of Intelligent Manufacturing, p. 1-12, 2015. http://dx.doi.org/10.1007/s10845-015-1046-4

TADEI, R.; GUPTA, J.N.D.; DELLA-CROCE, F.; CORTESI, M. Minimising makespan in the two-machine flow-shop with release times. Journal of the Operational Research Society, v. 49, p. 77-85, 1998. https://doi.org/10.2307/3010655

TANG, L.; LIU, P. Minimizing makespan in a two-machine flowshop scheduling with batching and release time. Mathematical and Computer Modelling, v. 49, p. 1071-1077, 2009. https://doi.org/10.1016/j.mcm.2008.09.012

TYAGI, N.; VARSHNEY, R.G.; CHANDRAMOULI, A.B. Six decades of flowshop scheduling research. International Journal of Scientific & Engineering Research, v. 4, n. 9, p. 854-864, 2013.

ZHOU, Z.; LI, X.; CHEN, H.; GUO, C. Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. International Journal of Production Research, p. 1-19, 2016. http://dx.doi.org/10.1080/00207543.2016.1140920




DOI: https://doi.org/10.14488/1676-1901.v18i1.2747

Métricas do artigo

Carregando Métricas ...

Metrics powered by PLOS ALM


R. Eletr. de Eng. de Produção e Correlatas - ISSN 1676-1901 Creative Commons License
Esta obra está licenciada sob uma Licença Creative Commons. © 2002 / Todos os direitos reservados Associação Brasileira de Engenharia de Produção (ABEPRO) Universidade Federal de Santa Catarina (UFSC).                           Contato: producaoonline@gmail.com