Uma heurística híbrida para o problema de escalonamento de tarefas em uma máquina com tempos de setup dependentes da sequência e datas de liberação
Resumo
Este trabalho aborda o problema de minimizar o tempo de conclusão em um escalonamento para uma máquina, considerando datas de liberação e tempos de configuração dependentes da sequência. Uma abordagem heurística híbrida que combina iterated local search e beam search é proposta. Para reduzir a complexidade computacional do algoritmo uma estratégia de avaliação eficiente de movimentos é utilizada durante a busca local. Foram realizados experimentos em 1800 instâncias da literatura, demonstrando que o algoritmo é capaz de obter soluções de alta qualidade em comparação com métodos existentes.
Referências
Fan, J., Öztop, H., Tasgetiren, M., and Gao, L. (2019). A variable block insertion heuristic for single machine with release dates and sequence dependent setup times for makespan minimization. In 2019 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1676–1683, Xiamen, China. IEEE.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fernandez-Viagas, V. and Costa, A. (2021). Two novel population based algorithms for the single machine scheduling problem with sequence dependent setup times and release times. Swarm and Evolutionary Computation, 63.
Graham, R., Lawler, E., Lenstra, J., and Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P.L. Hammer, E. J. and Korte, B., editors, Discrete Optimization II Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and Vancouver, volume 5 of Annals of Discrete Mathematics, pages 287 – 326. Elsevier.
Kindervater, G. and Savelsbergh, M. (1997). Vehicle routing: handling edge exchanges. In: Aarts, E., Lenstra, J. (Eds.), Local Search in Combinatorial Optimization. Wiley, New York, page 337–360.
Montoya-Torres, J., González-Solano, F., and Soto-Ferrari, M. (2012). Deterministic machine scheduling with release times and sequence-dependent setups using random-insertion heuristics. International Journal of Advanced Operations Management, 4(1/2):4–26.
Ovacikt, I. and Uzsoy, R. (1994). Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research, 32(6):1243–1263.
Pinedo, M. L. (2012). Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Nova Iorque.
Silva, J. M. P., Teixeira, E., and Subramanian, A. (2021). Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times. Journal of the Operational Research Society, 72(2):444–457.
Silva, M. M., Subramanian, A., Vidal, T., and Ochi, L. S. (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research, 221(3):513–520.
Velez-Gallego, M. C., Maya, J., and Montoya-Torres, J. (2016). A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan. Computers & Operations Research, 73:132–140.
Vidal, T., Crainic, T., Gendreau, M., and Prins, C. (2011). A unifying view on timing problems and algorithms. Cirrelt tech.rep. 2011-43, CIRRELT.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fernandez-Viagas, V. and Costa, A. (2021). Two novel population based algorithms for the single machine scheduling problem with sequence dependent setup times and release times. Swarm and Evolutionary Computation, 63.
Graham, R., Lawler, E., Lenstra, J., and Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P.L. Hammer, E. J. and Korte, B., editors, Discrete Optimization II Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Banff, Aha. and Vancouver, volume 5 of Annals of Discrete Mathematics, pages 287 – 326. Elsevier.
Kindervater, G. and Savelsbergh, M. (1997). Vehicle routing: handling edge exchanges. In: Aarts, E., Lenstra, J. (Eds.), Local Search in Combinatorial Optimization. Wiley, New York, page 337–360.
Montoya-Torres, J., González-Solano, F., and Soto-Ferrari, M. (2012). Deterministic machine scheduling with release times and sequence-dependent setups using random-insertion heuristics. International Journal of Advanced Operations Management, 4(1/2):4–26.
Ovacikt, I. and Uzsoy, R. (1994). Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research, 32(6):1243–1263.
Pinedo, M. L. (2012). Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Nova Iorque.
Silva, J. M. P., Teixeira, E., and Subramanian, A. (2021). Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times. Journal of the Operational Research Society, 72(2):444–457.
Silva, M. M., Subramanian, A., Vidal, T., and Ochi, L. S. (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research, 221(3):513–520.
Velez-Gallego, M. C., Maya, J., and Montoya-Torres, J. (2016). A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan. Computers & Operations Research, 73:132–140.
Vidal, T., Crainic, T., Gendreau, M., and Prins, C. (2011). A unifying view on timing problems and algorithms. Cirrelt tech.rep. 2011-43, CIRRELT.
Publicado
06/08/2023
Como Citar
MORAIS, Rafael; BULHÕES, Teobaldo; SUBRAMANIAN, Anand.
Uma heurística híbrida para o problema de escalonamento de tarefas em uma máquina com tempos de setup dependentes da sequência e datas de liberação. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 170-174.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230794.
