Uma heurística robusta para programação de máquinas paralelas com tempos de setup dependentes da sequência
DOI:
https://doi.org/10.14488/1676-1901.v17i2.2375Palavras-chave:
Programação da Produção. Máquinas paralelas. Setup dependente da sequência. Heurística.Resumo
O propósito deste trabalho foi elaborar uma heurística robusta e eficiente para o problema de programação de um conjunto de n tarefas com tempos de setup explícitos e dependentes da sequência em um conjunto de m máquinas de forma a minimizar o makespan (duração total da programação). Os resultados foram testados com instâncias artificiais baseadas em trabalhos publicados na literatura específica e comparados com um limitante inferior (lower bound) proposto a partir de um modelo de programação linear inteira mista. A qualidade da solução heurística foi medida com base no desvio percentual em relação ao limitante inferior. A experimentação demonstrou tanto a eficácia da solução, com desvio relativo médio de 5,51%, como a eficiência computacional da heurística, com tempos de execução desprezível.
Downloads
Referências
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
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.
