A robust heuristic for parallel machines scheduling problem with sequence-dependent setup times
DOI:
https://doi.org/10.14488/1676-1901.v17i2.2375Keywords:
Scheduling. Parallel machines. Sequence-dependent setup times. Heuristic.Abstract
This paper addresses the problem of minimizing makespan on m-parallel machine with setup times separated of processing times of jobs and sequence-dependent. A robust and efficient heuristic was proposed and computationally implemented. Results were tested by instances generated based on works of the specific literature and compared to a model of mixed integer linear programming proposed as a lower bound for the makespan. The quality of the heuristic solution was measured by percentage deviation of lower bound. Experiments demonstrated both the solution’s efficacy, with average relative deviation of 5.51%, and computational efficiency of the heuristic, with negligible execution times.
Downloads
References
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.
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
BAKER, K.R. Elements of Sequencing and Scheduling. Hanover: NH, 1995.
BEHNAMIAN, J.; FATEMI GHOMI, S.M.T. The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine. Information Science, v. 209, p. 181-196, 2013. https://doi.org/10.1016/j.ins.2012.07.020
BEHNAMIAN, J.; ZANDIEH, M.; FATEMI GHOMI, S.M.T. Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min-max technique. Soft Computing, v. 15, n. 7, p. 1313-1331, 2011. https://doi.org/10.1007/s00500-010-0673-0
BEHNAMIAN, J.; ZANDIEH, M.; FATEMI GHOMI, S.M.T. Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, v. 36, p. 9637-9644, 2009. https://doi.org/10.1016/j.eswa.2008.10.007
BILGE, U.; KIRAÇ, F.; KURTULAN, M.; PEKGUN, P. A tabu search algorithm for parallel machine total tardiness problem. Computers and Operations Research, v. 31, p. 397-414, 2004. https://doi.org/10.1016/S0305-0548(02)00198-3
BOZORGIRAD, M.A.; LOGENDRAN, R. Sequence-dependent group scheduling problem on unrelated-parallel machines. Expert Systems with Applications, v. 39, p. 9021-9030, 2012. https://doi.org/10.1016/j.eswa.2012.02.032
CHANG, P.; CHEN, S. Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times. Applied Soft Computing, v. 11, n. 1, p. 1263-1274, 2011. https://doi.org/10.1016/j.asoc.2010.03.003
CHANG, T.-Y.; CHOU, F.-D.; LEE, C.-E.; A heuristic algorithm to minimize total weighted tardiness on a single machine with release dates and sequence-dependent setup times. Journal of the Chinese Institute of Industrial Engineers, v. 21, n. 3, p. 289-300, 2004. https://doi.org/10.1080/10170660409509410
CHENG, T.C.E.; SIN, C.C.S. A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, v. 47, n. 3, p. 271-292, 1990. https://doi.org/10.1016/0377-2217(90)90215-W
CORREA, R.C.; FERREIRA, F.; REBREYEND, P. Scheduling multiprocessor tasks with genetic algorithms. IEEE Transactions on Parallel and Distributed Systems, v. 10, n. 8, p. 825-837, 1999. https://doi.org/10.1109/71.790600
DAMODARAN, P.; CHANG, P.-Y. Heuristics to minimize makespan of parallel batch processing machines. The International Journal of Advanced Manufacturing Technology, v. 37, n. 9, p. 1005-1013, 2008. https://doi.org/10.1007/s00170-007-1042-8
FOWLER, J.W.; HORNG, N.G.; COCHRAN, J.K. A hybridized genetic algorithm to solve parallel machine scheduling problems with sequence dependent setups. International Journal of Industrial Engineering – Theory Applications and Practice, v. 10, n. 3, p. 232-243, 2003.
FRIESEN, D.K. Tighter bounds for the MULTIFIT processor scheduling algorithm. SIAM Journal on Computing, v. 12, n. 1, p. 170-181, 1984. https://doi.org/10.1137/0213013
GENDREAU, M.; LAPORTE, G.; GUIMARÃES, E.M. A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times. European Journal of Operational Research, v. 133, p. 183-189, 2001. https://doi.org/10.1016/S0377-2217(00)00197-1
HOU, E.S.H.; ANSARI, N.; REN, H. A genetic algorithm for multiprocessor scheduling. IEEE Transactions on Parallel and Distributed Systems, v. 5, n. 2, p. 113-120, 1994. https://doi.org/10.1109/71.265940
HU, T.C. Parallel sequencing and assembly line problems. Operations Research, v. 9, n. 6, p. 941-848, 1961. https://doi.org/10.1287/opre.9.6.841
KASHAN, A.H.; KARIMI, B.; JENABI, M. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, v. 35, n. 4, p. 1084-1098, 2008. https://doi.org/10.1016/j.cor.2006.07.005
KIM, D.-W.; KIM, K.-H.; JANG, W.; CHEN, F.F. Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer Integrated Manufacturing, v. 18, n. 3-4, p. 223-231, 2002. https://doi.org/10.1016/S0736-5845(02)00013-3
KIM, S.S.; SHIN, H.J. Scheduling jobs on parallel machines: a restricted tabu search approach. International Journal of Advanced Manufacturing Technology, v. 22, p. 278-287, 2003. https://doi.org/10.1007/s00170-002-1472-2
KUO, W.-H.; HSU, C.; YANG, D.-L. Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects. Computers & Industrial Engineering, v. 61, n. 1, p. 179-183, 2011. https://doi.org/10.1016/j.cie.2011.03.008
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. https://doi.org/10.1080/00207540110064938
LAHA, D. A simulated annealing heuristic for minimizing makespan in parallel machine scheduling. Swarm, Evolutionary, and Memetic Computing, v. 7677, p. 198-205, 2012. https://doi.org/10.1007/978-3-642-35380-2_24
LEE, C.-Y.; MASSEY, J.D. Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Applied Mathematics, v. 20, n. 3, p. 233-242, 1988. https://doi.org/10.1016/0166-218X(88)90079-0
LEE, W.-C.; CHUANG, M.-C.; YEH, W.-C. Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Computers & Industrial Engineering, v. 63, p. 813-818, 2012. https://doi.org/10.1016/j.cie.2012.05.003
LEE, W.-C.; WU, C.-C.; CHEN, P. A simulated annealing approach to makespan minimization on identical parallel machines. The International Journal of Advanced Manufacturing Technology, v. 31, n. 3, p. 328-334, 2006. https://doi.org/10.1007/s00170-005-0188-5
LI, K.; YANG, S.-L.; MA, H.-W. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines. Mathematical and Computer Modelling, v. 53, p. 854-860, 2011. https://doi.org/10.1016/j.mcm.2010.10.022
LIAEE, M.M.; EMMONS, H. Scheduling families of jobs with setup times. International Journal of Production Economics, Amsterdam, v. 51, n. 3, p. 165-176, 1997. https://doi.org/10.1016/S0925-5273(96)00105-3
LIN, S.-W.; LU, C.-C.; YING, K.-C. Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints. The International Journal of Advanced Manufacturing Technology, v. 53, p. 353-361, 2011. https://doi.org/10.1007/s00170-010-2824-y
LIN, Y.-K. Fast LP models and algorithms for identical jobs on uniform parallel machines. Applied Mathematical Modelling, v. 37, p. 3436-3448, 2013. https://doi.org/10.1016/j.apm.2012.07.023
LIN, Y.-K.; FOWLER, J.W.; PFUND, M.E. Multiple-objective heuristics for scheduling unrelated parallel machines. European Journal of Operational Research, v. 227, n. 2, p. 239-253, 2013. https://doi.org/10.1016/j.ejor.2012.10.008
McNAUGHTON, R. Scheduling with deadlines and loss functions. Management Science, v. 6, n. 1, p. 1-12, 1959. https://doi.org/10.1287/mnsc.6.1.1
MENDES, A.S.; MULLER, F.M.; FRANÇA, P.M.; MOSCATO, P. Comparing meta-heuristic approaches for parallel machine scheduling problems. Production Planning and Control, v. 13, n. 2, p. 143-154, 2002. https://doi.org/10.1080/09537280110069649
MIN, L.; CHENG, W. Identical parallel machine scheduling problem for minimizing the makespan using genetic algorithm combined by simulated annealing. Chinese Journal of Electronics, v. 7, n. 4, p. 317-321, 1998.
MOKOTOFF, E. Parallel machine scheduling problems: a survey. Asia-Pacific Journal of Operational Research, v. 18, n. 1, p. 193-242, 2001.
MONMA, C.L.; POTTS, C.N. On the complexity of scheduling with batch setup times. Operations Research, v. 37, n. 5, p. 798-804, 1989. https://doi.org/10.1287/opre.37.5.798
MONTOYA-TORRES, J. R.; SOTO-FERRARI, M.; GONZÁLEZ-SOLANO, F. Production scheduling with sequence-dependent setups and job release times. Dyna, v. 77, n. 163, p. 260-269, 2010.
MONTOYA-TORRES, J. R.; SOTO-FERRARI, M.; GONZÁLEZ-SOLANO, F.; ALFONSO-LIZARAZO, E.H. Machine scheduling with sequence-dependent setup times using a randomized search heuristic. IEEE – International Conference on Computers & Industrial Engineering, p. 28-33, 2009. https://doi.org/10.1109/iccie.2009.5223742
MORA, B.; MOSHEIOV, G. Batch scheduling on uniform machines to minimize total flow-time. Computers & Operations Research, v. 39, n. 3, p. 571-575, 2012. https://doi.org/10.1016/j.cor.2011.05.014
MUNTZ, R.R.; COFFMAN, E.G. Optimal preemptive scheduling on two-processor systems. IEEE Transactions on Computers, v. 18, n. 11, p. 1014-1020, 1969. https://doi.org/10.1109/T-C.1969.222573
NAIT, T. D.; CHU, C.; YALAOUI, F.; AMODEO, L. A new approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times based on linear programming. International Conference on Industrial Engineering and Production Management (IEPM-03), v. 3, p. 266-274, 2003.
OVACIK, I.M.; UZHOY, R. Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times. Operations Research Letters, v. 14, n. 5, p. 251-256, 1993. https://doi.org/10.1016/0167-6377(93)90089-Y
PINEDO, M. Scheduling: Theory, Algorithms, and Systems. New Jersey: Prentice-Hall, 2016.
RADHAKRISHNAN, S.; VENTURA, J.A. Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times. International Journal of Production Research, v. 38, n. 10, p. 2233-2252, 2000. https://doi.org/10.1080/00207540050028070
RAJGOPAL, J.; BIDANDA, B. On scheduling parallel machines with two setup classes. International Journal of Production Research, v. 29, n. 12, p. 2443-2458, 1991. https://doi.org/10.1080/00207549108948095
RUIZ, R.; ANDRÉS-ROMANO, C. Scheduling unrelated parallel machines with resource-assignable sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, v. 57, p. 777-794, 2011. https://doi.org/10.1007/s00170-011-3318-2
SANTOS, F.C.; VILARINHO, P.M. The problem of scheduling in parallel machines: a case study. Proceedings of the World Congress on Engineering, v. 3, 2010.
SVELTANA, A.; KRAVCHENKO, S.; WERNER, F. A heuristic algorithm for minimizing mean flow time with unit setups. Information Processing Letters, v. 79, p. 291-296, 2001. https://doi.org/10.1016/S0020-0190(01)00136-3
TURKER, A. K.; SEL, C. Scheduling two parallel machines with sequence dependent setups and a single server. Gazy University Journal of Science, v. 24, n. 1, p. 113-123, 2011.
VALLADA, E.; RUIZ, R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, v. 211, n. 3, p. 612-622, 2011. https://doi.org/10.1016/j.ejor.2011.01.011
VAN HOP, N.; NAGARUR, N.N. The scheduling problem of PCBs for multiple non-identical parallel machines. European Journal of Operational Research, v. 158, p. 577-594, 2004. https://doi.org/10.1016/S0377-2217(03)00376-X
WENG, M.X.; LU, J.; REN, H. Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, v. 70, n. 3, p. 215-226, 2001. https://doi.org/10.1016/S0925-5273(00)00066-9
YANG, D.-L.; YANG, S.-J. Unrelated parallel-machine scheduling problems with multiple rate-modifying activities. Information Sciences, v. 235, p. 280-286, 2013. https://doi.org/10.1016/j.ins.2013.02.013
ZHU, X.; WILHELM, W.E. Scheduling and lot sizing with sequence-dependent setup: a literature review. IIE Transactions, v. 38, p. 987-1007, 2006. https://doi.org/10.1080/07408170600559706
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 .
