Abstract: Параллельные вычисления с использованием графических ускорителей вызывают большой интерес при решении задач дискретной оптимизации. Методы полного или частичного перебора для NP-трудных задач требуют большого объема вычислений, и в тех случаях, когда параллельная реализация метода оказывается возможной, эффект от применения графического процессора может быть очень значительным. Алгоритмы локального поиска обычно лучше всего подходят для распараллеливания, при этом они хорошо зарекомендовали себя с точки зрения качества получаемых решений. В данном докладе обсуждается реализация алгоритма локального поиска с многократным перезапуском для одной прикладной задачи составления производственных расписаний. Приводятся результаты экспериментов и их сравнение с другими подходами.

Cite: Борисовский П.А.
Решение задачи составления производственного расписания с помощью параллельного алгоритма локального поиска на GPU
XVIII Российская конференция с международным участием "Распределенные информационно-вычислительные ресурсы" 05-08 дек. 2022