Параллельный алгоритм «иди с победителями» для некоторых задач составления расписаний

Параллельный алгоритм «иди с победителями» для некоторых задач составления расписаний

Борисовский П. А.
Дискретный анализ и исследование операций, 30, 4, 5-23 (2023)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2023.30.773

Аннотация:

Рассматривается подход к решению перестановочных задач составления расписаний с использованием графических ускорителей. Предложен параллельный эволюционный алгоритм на основе итеративного случайного локального поиска и алгоритма «иди с победителями». Проведён вычислительный эксперимент на тестовых примерах классической задачи Flow Shop и прикладной задачи составления производственного расписания с временными окнами. Результаты показывают высокую скорость и хорошую точность получаемых решений по сравнению с различными вариантами генетического алгоритма, а также пакетом Gurobi. Предложенный подход отличается простотой реализации, удобством адаптации к особенностям высокопроизводительных графических вычислений и может применяться для решения практических задач. 
Табл. 3, библиогр. 18.

Литература:
  1. Metaheuristics for production scheduling. London: ISTE; Hoboken, NJ: Wiley, 2013. 528 p.
     
  2. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах. Введение в программирование графических процессоров. М.: ДМК Пресс, 2013. 232 с.
     
  3. Essaid M., Idoumghar L., Lepagnot J., Brévilliers M. GPU parallelization strategies for metaheuristics: A survey // Int. J. Parallel Emerg. Distrib. Syst. 2019. V. 34, No. 5. P. 497–522.
     
  4. Borisovsky P., Kovalenko Yu. A memetic algorithm with parallel local search for flowshop scheduling problems // Bioinspired optimization methods and their applications. Proc. 9th Int. Conf. (Brussels, Belgium, Nov. 19–20, 2020). Cham: Springer, 2020. P. 201–213. (Lect. Notes Comput. Sci.; V. 12438).
     
  5. Cheng J. R., Gen M. Accelerating genetic algorithms with GPU computing: A selective overview // Comput. Ind. Eng. 2019. V. 128. P. 514–525.
     
  6. Luo J., Fujimura S., el Baz D., Plazolles B. GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem // J. Parallel Distrib. Comput. 2019. V. 133. P. 244–257.
     
  7. Борисовский П. А. Решение задачи составления производственного расписания с помощью параллельного алгоритма локального поиска на GPU // Сб. тр. XVIII Рос. конф. с междунар. участием «Распределённые информационно-вычислительные ресурсы» (Новосибирск, Россия, 5–8 дек. 2022 г.). Новосибирск: ФИЦ ИВТ, 2022. C. 16–19.
     
  8. Berndorfer J., Parragh S. N. Modeling and solving a real world machine scheduling problem with due windows and processing set restrictions // Procedia Comput. Sci. 2022. V. 200. P. 1646–1653.
     
  9. Aldous D., Vazirani U. «Go with the winners» algorithms // Proc. 35th Annu. Symp. Foundations of Computer Science (Santa Fe, USA, Nov. 20–22, 1994). Los Alamitos, CA: IEEE Comput. Soc., 1994. P. 492–501.
     
  10. Brizuela C. A., Gutiérrez E. Multi-objective go with the winners algorithm: A preliminary study // Evolutionary multi-criterion optimization. Proc. 3rd Int. Conf. (Guanajuato, Mexico, Mar. 9–11, 2005). Heidelberg: Springer, 2005. P. 206–220. (Lect. Notes Comput. Sci.; V. 3410).
     
  11. Ebert T., Goldstein D. A «Go with the winners» approach to finding frequent patterns // Proc. 20th Annu. ACM Symp. Applied Computing (Santa Fe, USA, Mar. 13–17, 2005). New York: ACM, 2005. P. 498–502.
     
  12. Peinado M., Lengauer T. Parallel «Go with the winners» algorithms in the LogP model // Proc. 11th Int. Parallel Processing Symp. (Geneva, Switzerland, Apr. 1–5, 1997). Los Alamitos, CA: IEEE Comput. Soc., 1997. P. 656–664. 
     
  13. Juan A. A., Lourenço H., Mateo M., Luo R., Castella Q. Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues // Int. Trans. Oper. Res. 2014. V. 21, No. 1. P. 103–126.
     
  14. Reeves C. R. A genetic algorithm for flowshop sequencing // Comput. Oper. Res. 1995. V. 22, No. 1. P. 5–13.
     
  15. Taillard E. Some efficient heuristic methods for the flow shop sequencing problem // Eur. J. Oper. Res. 1990. V. 47, No. 1. P. 65–74.
     
  16. Umam M. S., Mustafid M., Suryono S. A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem // J. King Saud Univ. — Comput. Inf. Sci. 2022. V. 34, No. 9. P. 7459–7467.
     
  17. Evolutionary computation 1: Basic algorithms and operators. New York: Taylor & Francis, 2000. 340 p.
     
  18. Grabowski J., Wodecki M. A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion // Comput. Oper. Res. 2004. V. 31, No. 11. P. 1891–1909.

Исследование выполнено за счёт гранта Российского научного фонда (проект № 22–71–10015).

Борисовский Павел Александрович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: pborisovsky@ofim.oscsbras.ru

Статья поступила 12 мая 2023 г. 
После доработки — 7 августа 2023 г. 
Принята к публикации 20 августа 2023 г.

Abstract:

We consider an approach to solving permutation scheduling problems using graphics accelerators. A parallel evolutionary algorithm based on the iterated random local search and the “Go with the winners” algorithm is proposed. A computational experiment was carried out on test instances of the classic Flow Shop problem and one applied production scheduling problem with time windows. The results show high computing speed and good accuracy of obtained solutions in comparison with various variants of the genetic algorithm and Gurobi solver. The proposed approach is easy to implement and convenient for adaptation to particular features of graphics computing and can be used to solve practical problems. 
Tab. 3, bibliogr. 18.

References:
  1. Metaheuristics for Production Scheduling (ISTE, London; Wiley, Hoboken, NJ, 2013).
     
  2. J. Sanders and E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming (Addison–Wesley, 2011; DMK Press, Moscow, 2013 [Russian]).
     
  3. M. Essaid, L. Idoumghar, J. Lepagnot, and M. Brévilliers, GPU parallelization strategies for metaheuristics: A survey, Int. J. Parallel Emerg. Distrib. Syst. 34 (5), 497–522 (2019). 
     
  4. P. Borisovsky and Y. Kovalenko, A memetic algorithm with parallel local search for flowshop scheduling problems, in Bioinspired Optimization Methods and Their Applications (Proc. 9th Int. Conf., Brussels, Belgium, Nov. 19- 20, 2020) (Springer, Cham, 2020), pp. 201–213 (Lect. Notes Comput. Sci., Vol. 12438).
     
  5. J. R. Cheng and M. Gen, Accelerating genetic algorithms with GPU computing: A selective overview, Comput. Ind. Eng. 128, 514–525 (2019).
     
  6. J. Luo, S. Fujimura, D. el Baz, and B. Plazolles, GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem, J. Parallel Distrib. Comput. 133, 244–257 (2019).
     
  7. P. A. Borisovsky, Solving one production scheduling problem using parallel local search algorithm on GPU, in Proc. XVIII Russian Conf. Int. Particip. “Distributed Information and Computational Resources”, Novosibirsk, Russia, Dec. 5–8, 2022 (Inst. Vychisl. Technol., Novosibirsk, 2022), pp. 16–19 [Russian].
     
  8. J. Berndorfer and S. N. Parragh, Modeling and solving a real world machine scheduling problem with due windows and processing set restrictions, Procedia Comput. Sci. 200, 1646–1653 (2022).
     
  9. D. Aldous and U. Vazirani, “Go with the winners” algorithms, in Proc. 35th Annu. Symp. Foundations of Computer Science, Santa Fe, USA, Nov. 20-22, 1994 (IEEE Comput. Soc., Los Alamitos, CA, 1994), pp. 492–501. 
     
  10. C. A. Brizuela and E. Gutiérrez, Multi-objective go with the winners algorithm: A preliminary study, in Evolutionary Multi-Criterion Optimization (Proc. 3rd Int. Conf., Guanajuato, Mexico, Mar. 9–11, 2005) (Springer, Heidelberg, 2005), pp. 206–220 (Lect. Notes Comput. Sci., Vol. 3410).
     
  11. T. Ebert and D. Goldstein, A “Go with the winners” approach to finding frequent patterns, in Proc. 20th Annu. ACM Symp. Applied Computing, Santa Fe, USA, Mar. 13–17, 2005 (ACM, New York, 2005), pp. 498–502.
     
  12. M. Peinado and T. Lengauer, Parallel “Go with the winners” algorithms in the LogP model, in Proc. 11th Int. Parallel Processing Symp., Geneva, Switzerland, Apr. 1–5, 1997 (IEEE Comput. Soc., Los Alamitos, CA, 1997), pp. 656–664.
     
  13. A. A. Juan, H. Lourenço, M. Mateo, R. Luo, and Q. Castella, Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues, Int. Trans. Oper. Res. 21 (1), 103–126 (2014).
     
  14. C. Reeves, A genetic algorithm for flow-shop sequencing, Comput. Oper. Res. 22 (1), 5–13 (1995).
     
  15. E. Taillard, Some efficient heuristic methods for the flow shop sequencing problem, Eur. J. Oper. Res. 47, 65–74 (1990).
     
  16. M. S. Umam, M. Mustafid, and S. Suryono, A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem, J. King Saud Univ. — Comput. Inf. Sci. 34 (9), 7459–7467 (2022). 
     
  17. Evolutionary Computation 1: Basic Algorithms and Operators (Taylor & Francis, New York, 2000). 
     
  18. J. Grabowski and M. Wodecki, A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Comput. Oper. Res. 31 (11), 1891–1909 (2004).