Текущий выпуск Выпуск 1, 2017 Том 27

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

 pdf (280K)

Исследование посвящено построению параллельного алгоритма решения задачи «на узкие места», связанного с поиском разбиения конечного множества заданий на конечное число исполнителей (работников). Описывается алгоритм нахождения оптимального разбиения заданий с использованием метода динамического программирования с элементами параллельных вычислений при построении массива значений функции Беллмана. Выполнена оценка вычислительной сложности двух алгоритмов (с использованием и без использования параллельной структуры). Создана программа, с помощью которой проведен вычислительный эксперимент по решению поставленной задачи на суперкомпьютере «УРАН». Выполнен сравнительный анализ реализации алгоритмов как с использованием, так и без использования параллельной структуры. Представлена зависимость времени счета реализованной программы на суперкомпьютере от количества вычислительных ядер.

Ключевые слова: динамическое программирование, разбиение, параллельный алгоритм
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2017, т. 27, вып. 1, с. 129-137
DOI: 10.20537/vm170111

Solution of the problem of optimal task distribution by the method of dynamic programming with parallel computing

The aim of the study is to construct a parallel algorithm for solving a bottleneck (minmax) problem connected with partitioning a finite set of tasks between a finite number of agents. We describe the algorithm of finding an optimal partition of tasks through dynamic programming with a parallel computation of the Bellman function and provide a computational complexity estimate for the two algorithms (with and without the parallel construction). The algorithm was implemented for the Uran supercomputer, and a computational experiment was conducted; computation time was measured for the serial algorithm and for the parallel one on varying numbers of processor cores.

Keywords: dynamic programming, partition, parallel algorithm
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2017, vol. 27, issue 1, pp. 129-137

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref