A computational study of new priority rules for flow shop problem with setup times and different release dates

Authors

  • Caio Soares de Araújo Universidade Federal de Goiás / Regional Catalão
  • Helio Yochihiro Fuchigami Universidade Federal de Goiás / Faculdade de Ciências e Tecnologia

DOI:

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

Keywords:

Scheduling. Flow shop. Priority rules. Sequence-independent setup times. Release dates.

Abstract

This research deals with the flow shop production system with sequence-independent setup times, different job release dates and two distinct problems: makespan and total flowtime minimization. It was undertaken a large computational study of the performance of new priority rules, widely used in practice by companies and defined here based on the structure of the problems analyzed. As is well known, the computational efficiency of the priority rules as solution methods is already presumed. Therefore, this work focused on the analysis of the effectiveness, i.e., the quality of the solution reached by the application of such rules in the two problems considered. The results proved the applicability of the proposed methods and identified the best rules for each case, with their respective ordering criteria.

Downloads

Download data is not yet available.

Author Biographies

Caio Soares de Araújo, Universidade Federal de Goiás / Regional Catalão

Mestrado em Gestão Organizacional

Helio Yochihiro Fuchigami, Universidade Federal de Goiás / Faculdade de Ciências e Tecnologia

Engenharia de Produção / Pesquisa Operacional

References

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

Published

2018-03-15

How to Cite

Araújo, C. S. de, & Fuchigami, H. Y. (2018). A computational study of new priority rules for flow shop problem with setup times and different release dates. Revista Produção Online, 18(1), 207–237. https://doi.org/10.14488/1676-1901.v18i1.2747

Issue

Section

Papers