A computational study of new priority rules for flow shop problem with setup times and different release dates
DOI:
https://doi.org/10.14488/1676-1901.v18i1.2747Keywords:
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
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
How to Cite
Issue
Section
License
The Journal reserves the right to make spelling and grammatical changes, aiming to keep a default language, respecting, however, the style of the authors.
The published work is responsibility of the (s) author (s), while the Revista Produção Online is only responsible for the evaluation of the paper. The Revista Produção Online is not responsible for any violations of Law No. 9.610 / 1998, the Copyright Act.
The journal allows the authors to keep the copyright of accepted articles, without restrictions
This work is licensed under a Creative Commons License .
