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

• Rafael Morais UFPB
• Teobaldo Bulhões UFPB
• Anand Subramanian UFPB

DOI: https://doi.org/10.5753/etc.2023.230794

Abstract

This paper addresses the problem of minimizing the makespan on a single machine scheduling, considering release dates and non-anticipatory, sequence dependent setup times. A hybrid heuristic approach that combines iterated local search with beam search is proposed. To reduce the computational complexity of the algorithm, an efficient move evaluation strategy is employed during the local search. Experiments were performed on 1800 instances from the literature, demonstrating that the algorithm is capable of obtaining highquality solutions when compared to existing methods.

References

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.