Спросить
Войти
ISSN 1560-3644 ИЗВЕСТИЯ ВУЗОВ. СЕВЕРО-КАВКАЗСКИЙ РЕГИОН._ТЕХНИЧЕСКИЕ НАУКИ. 2020. № 2
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ INFORMATICS, COMPUTER ENGINEERING AND CONTROL
УДК 681.3.681.5 DOI: 10.17213/1560-3644-2020-2-5-12
ИССЛЕДОВАНИЕ РАЗЛИЧНЫХ МОДИФИКАЦИЙ АЛГОРИТМА ПЛОТНИКОВА-ЗВЕРЕВА ПРИ РЕШЕНИИ НЕОДНОРОДНОЙ
МИНИМАКСНОЙ ЗАДАЧИ
© 2020 г. В.Г. Кобак, В.М. Поркшеян, А.П. Кузин
Донской государственный технический университет, г. Ростов-на-Дону, Россия
INVESTIGATION OF VARIOUS MODIFICATIONS OF THE PLOTNIKOV-ZVEREV ALGORITHM WHEN SOLVING AN INHOMOGENEOUS MINIMAX PROBLEM
V.G. Kobak, V.M. Porksheyan, A.P. Kuzin
Don State Technical University, Rostov-on-Don, Russia
Кобак Валерий Григорьевич - д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Поркшеян Виталий Маркосович - канд. физ.-мат. наук, доцент, кафедра «Математика», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: spu-46@donstu.ru
Кузин Александр Павлович - ст. преподаватель, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: alexpavkuzin@gmail.com
Рассматривается проблема решения неоднородной минимаксной задачи, являющейся одной из задач теории оптимизации. Сложность данной задачи заключается в том, что получить точное решение для больших размерностей не представляется возможным. Анализируется один из приближенных методов решения, называемый алгоритмом Плотникова-Зверева. Кроме того, описываются несколько модификаций данного алгоритма, разработанных авторами статьи. При помощи вычислительных средств был поставлен численный эксперимент, в рамках которого проводилось сравнение алгоритма Плотникова-Зверева и его модификаций по следующим критериям: минимальное значение и среднее значение среди полученных решений. В результате был сделан вывод о высокой эффективности разработанных модификаций алгоритма.
Kobak Valeriy G. - Doctor of Technical Sciences, Professor, Department «The Software of Computer Facilities and the Automated Systems», Don State Technical University, Rostov-on-Don, Russia. E-mail: valera33305@mail.ru
Porksheyan Vitaliy M. - Candidate of Physical and Mathematical Sciences, Associate Professor, Department «Mathematics», Don State Technical University, Rostov-on-Don, Russia. E-mail: spu-46@donstu.ru
Kuzin Alexandr P. - Senior Lecturer, Department «The Software of Computer Facilities and the Automated Systems», Don State Technical University, Rostov-on-Don, Russia. E-mail: alexpavkuzin@gmail.com
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
The article deals with the problem of solving heterogeneous minimax problem, which is one of the problems of optimization theory. The complexity of this problem is that to get an accurate solution for in higher dimensions it is not possible. The article discusses one of the approximate solution methods called the Plotnikov-Zverev algorithm. In addition, several modifications of this algorithm are described, developed by the authors of the article. As part of the study, using a numerical experiment was set up in the framework of computer tools the Plotnikov-Zverev algorithm was compared with its modifications based on the following criteria: minimum value and average value among the received solutions. During a computational experiment the conclusion was made about the high efficiency of the developed modifications algorithm&s.
Постановка задачи
При решении NP--полных задач теории расписаний [1] точные методы эффективны только для малой размерности задач. Для решения задач большей размерности используются приближенные алгоритмы, основанные на определенных эвристических приемах [1 - 4]. Одним из таких алгоритмов является алгоритм Плотникова-Зверева [5-7], который ориентирован на решение неоднородной минимаксной задачи.
В терминах теории расписаний однородная минимаксная задача может быть сформулирована следующим образом. Имеется система обслуживания, состоящая из N независимых устройств P = {p1,p2,...,pn} . На обслуживание поступает конечный поток М - множество независимых параллельных заданий (функциональных операторов) T = {tl312,...,tm}; T(tipj)- длительность
обслуживания задания ti устройством pj, определяется матрицей Тх. Приборы в общем случае не идентичны, задание ti может быть обслужено любым из устройств, и устройство pj может обрабатывать одновременно не более одного задания. Необходимо определить такое распределение заданий по устройствам без прерываний, чтобы время выполнения всей совокупности заданий было минимальным. Критерием минимизации времени выполнения заданий является минимаксный критерий, который определяется в следующем виде: f = max f ^ min ,
l<J<n J
где fj = ^ x(tiPj) - время завершения раT(tiPj )eT
боты процессораpj [5].
Теоретическая часть.
Алгоритм Плотникова-Зверева
Базовый алгоритм Плотникова-Зверева для решения неоднородной минимаксной задачи состоит из следующих шагов [1].
Шаг 1: матрица задач сортируется в зависимости от суммы элементов в каждой строке по убыванию.
Шаг 2: формируется одномерный массив нагрузки, размер которого равен количеству устройств обработки. На первом этапе он заполняется нулями.
Шаг 3: к каждой строке прибавляются значения из массива загрузки. После чего ищется минимальный элемент и сохраняется его номер в строке матрицы п_шт.
Шаг 4: значение минимального элемента прибавляется к соответствующему ему элементу массива загрузки с индексом п_шт, и его номер заносится в список решений.
Шаг 5: алгоритм выполняется до тех пор, пока не будут обработаны все строки матрицы.
Возьмем для примера матрицу, изображенную на рис. 1.
№ строки Прибор 1 Прибор 2 Прибор 3
Рис. 1. Исходная матрица задач / Fig. 1. The initial matrix of tasks
Отсортируем строки по убыванию сумм, как показано на рис. 2:
№ строки Прибор 1 Прибор 2 Прибор 3 Сумма
Рис. 2. Отсортированная матрица задач / Fig. 2. Sorted task matrix
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
Найдем минимальный элемент в первой строке. Он равен 7 и имеет индекс 1. Индекс найденного элемента заносится в список решений. А первый элемент массива загрузки становится равен 7 (рис. 3).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 7 0 0
Список решений
Рис. 3. Первый шаг алгоритма Плотникова-Зверева / Fig. 3. The first step of the Plotnikov-Zverev algorithm
Прибавим ко второй строке содержимое массива загрузки. Найдем минимальный элемент во второй строке. Он равен 3 и имеет индекс 2. Индекс найденного элемента заносится в список решений. Второй элемент массива загрузки становится равен 3 (рис. 4).
№ строки Прибор 1 Прибор 2 Прибор 3
Список решений
Прибавим к четвертой строке содержимое массива загрузки. Найдем минимальный элемент в четвертой строке. Он равен 8 и имеет индекс 2. Индекс найденного элемента заносится в список решений. К первому элементу массива загрузки прибавляется исходное значение 5 (рис. 6).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 7 8 6
Список решений
Рис. 6. Четвертый шаг алгоритма Плотникова-Зверева / Fig. 6. The fourth step of the Plotnikov-Zverev algorithm
Прибавим к пятой строке содержимое массива загрузки. Найдем минимальный элемент в пятой строке. Он равен 10 и имеет индекс 1. Индекс найденного элемента заносится в список решений. К первому элементу массива загрузки прибавляется 3 (рис. 7).
№ строки Прибор 1 Прибор 2 Прибор 3
Список решений
Массив 7 3 0
загрузки
Массив 10 8 6
загрузки
Рис. 4. Второй шаг алгоритма Плотникова-Зверева / Fig. 4. The second step of the Plotnikov-Zverev algorithm
Прибавим к третьей строке содержимое массива загрузки. Найдем минимальный элемент в третьей строке. Он равен 6 и имеет индекс 3. Индекс найденного элемента заносится в список решений. Третий элемент массива загрузки становится равен 6 (рис. 5).
Рис. 7. Пятый шаг алгоритма Плотникова-Зверева / Fig. 7. The fifth step of the Plotnikov-Zverev algorithm
Прибавим к шестой строке содержимое массива загрузки. Найдем минимальный элемент в шестой строке. Он равен 8 и имеет индекс 3. Индекс найденного элемента заносится в список решений. К третьему элементу массива загрузки
№ строки Прибор 1 Прибор 2 Прибор 3
Список решений
прибавляется 2 (рис. 8).
№ строки Прибор 1 Прибор 2 Прибор 3
Список решений
Массив 7 3 6
загрузки
Массив 10 8 8
загрузки
Рис. 5. Третий шаг алгоритма Плотникова-Зверева Рис. 8. Шестой шаг алгоритма Плотникова-Зверева
/ Fig. 5. The third step of the Plotnikov-Zverev algorithm / Fig. 8. The sixth step of the Plotnikov-Zverev algorithm
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION.
TECHNICAL SCIENCE. 2020. No 2
По итогу работы алгоритма было получено решение {1 2 3 2 1 3}. Рассчитаем загрузку по каждому устройству Р1 = 7 + 3 = 10, Р2 = 3 + 5 = 8, Р3 = 6 + 2 = 8. Возьмем максимальную полученную нагрузку, которая и будет итоговым решением ^МтМах= 9.
Метод минимальных элементов
Шаг 1: матрица задач сортируется в зависимости от суммы элементов в каждой строке по убыванию.
Шаг 2: формируется одномерный массив нагрузки, размер которого равен количеству устройств обработки. На первом этапе он заполняется нулями.
Шаг 3: в каждой строке выбирается минимальный элемент и сохраняется его номер в строке матрицы п_тт.
Шаг 4: значение минимального элемента прибавляется к соответствующему ему элементу массива загрузки с индексом п_тт, и его номер заносится в список решений.
Шаг 5: алгоритм выполняется до тех пор, пока не будут обработаны все строки матрицы.
Возьмем для примера матрицу из предыдущего примера и также ее отсортируем (рис. 9).
№ строки Прибор 1 Прибор 2 Прибор 3 Сумма
Рис. 9. Первый шаг алгоритма метода минимальных элементов / Fig. 9. The first step of the minimal elements method
Найдем минимальный элемент в первой строке. Он равен 7 и имеет индекс 1. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к первому элементу матрицы загрузки (рис. 10).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 7 0 0
Список решений
Рис. 10. Второй шаг алгоритма метода минимальных элементов / Fig. 10. The second step of the minimal elements method
Найдем минимальный элемент во второй строке. Он равен 3 и имеет индекс 2. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к второму элементу матрицы загрузки (рис. 11).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 7 3 0
Список решений
Рис. 11. Третий шаг алгоритма метода минимальных элементов / Fig. 11. The third step of the minimal elements method
Найдем минимальный элемент в третьей строке. Он равен 4 и имеет индекс 1. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к первому элементу матрицы загрузки (рис. 12).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 11 3 0
Список решений
Рис. 12. Четвертый шаг алгоритма метода минимальных элементов / Fig. 12. The fourth step of the minimum element method
Найдем минимальный элемент в четвертой строке. Он равен 4 и имеет индекс 3. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к третьему элементу матрицы
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 11 3 4
Список решений
Рис. 13. Пятый шаг алгоритма метода минимальных элементов / Fig. 13. The fifth step of the minimum element method
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION.
TECHNICAL SCIENCE. 2020. No 2
Найдем минимальный элемент в пятой строке. Он равен 3 и имеет индекс 1. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к первому элементу матрицы загрузки (рис. 14).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 14 3 4
Список решений
Рис. 14. Шестой шаг алгоритма метода минимальных элементов / Fig. 14. The sixth step of the minimum element method
Найдем минимальный элемент в шестой строке. Он равен 2 и имеет индекс 3. Индекс найденного элемента заносится в список решений. Прибавляем значение найденного минимального элемента к третьему элементу матрицы загрузки (рис. 15).
№ строки Прибор 1 Прибор 2 Прибор 3
Массив загрузки 14 3 6
Список решений
Рис. 15. Седьмой шаг алгоритма метода минимальных элементов / Fig. 15. The seventh step of the minimum element method
По итогу работы алгоритма было получено решение {1 21 3 1 3}. Рассчитаем загрузку по каждому устройству Рх = 7 + 4 + 3 = 14, P2 = 3, P3 = 4 + 2 = 6. Возьмем максимальную полученную нагрузку Рь которая и будет итоговым решением ^MmMax=14.
Модификация алгоритма Плотникова-Зверева с быстрой
остановкой Авторами был разработан алгоритм с быстрой остановкой, который достаточно хорошо работает для различных диапазонов значений загрузки. Данный алгоритм был назван - «модификация алгоритма Плотникова-Зверева с быстрой остановкой с критерием по средним элементам» и состоит из следующих шагов.
Шаг 1: матрица задач сортируется в зависимости от суммы элементов в каждой строке по убыванию.
Шаг 2: формируется одномерный массив нагрузки, размер которого равен количеству устройств обработки. На первом этапе он заполняется нулями.
Шаг 3: выполняется расчет критерия переключения алгоритма. Находится сумма средних значений элементов в каждой строке и делится на количество приборов.
Шаг 4: в текущей строке ищется минимальный элемент. Если его значение в сумме с элементом массива загрузки меньше или равно критерию переключения, то этот элемент прибавляется к массиву загрузки, а его индекс заносится в список решений, иначе алгоритм заканчивается и переключается на алгоритм Плотникова-Зверева.
Результаты экспериментальных исследований
В рамках эксперимента сравнивалась эффективность работы алгоритма Плотникова-Зверева и метода минимальных элементов [8 - 10]. В качестве оценки использовались среднее и минимальное значения минимаксных критериев, полученные в ходе 500 экспериментов для разных матриц.
Обобщённые результаты эксперимента для 500 различных матриц заданий для 3, 4, 5, 6, 7, 8, 9 и 10 приборов, содержащих значения в диапазоне от 10 до 50, представлены в табл. 1.
Обобщённые результаты эксперимента для 500 различных матриц заданий для 3, 4, 5, 6, 7, 8, 9 и 10 приборов, содержащих значения в диапазоне от 25 до 35, представлены в табл. 2.
Как видно из эксперимента, для широкого разброса значений подавляющее преимущество имеет метод минимальных элементов, а при узком диапазоне ситуация диаметрально противоположная.
Для проверки эффективности алгоритма, разработанного авторами, был поставлен вычислительный эксперимент, результаты которого представлены ниже.
Обобщённые результаты эксперимента для 500 различных матриц заданий для 3, 4, 5, 6, 7, 8, 9 и 10 приборов, содержащих значения в диапазоне от 25 до 35, представлены в табл. 3.
Обобщённые результаты эксперимента для 500 различных матриц заданий для 3, 4, 5, 6, 7, 8, 9 и 10 приборов, содержащих значения в диапазоне от 10 до 50, представлены в табл. 4.
ISSN 1560-3644 ИЗВЕСТИЯ ВУЗОВ. СЕВЕРО-КАВКАЗСКИЙ РЕГИОН._ТЕХНИЧЕСКИЕ НАУКИ. 2020. № 2
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
Таблица 1 / Table 1
Результаты вычислительного эксперимента с загрузкой 10...50 / Results of a computational experiment with a load of 10...50
Число заданий Метод Критерий 3 4 5 6 7 8 9 10
Мин значение 817 544 438 365 294 274 242 237
Плотников-Зверев Среднее значение 900 683 503 417 372 354 293 285
Мин значение 831 603 439 359 330 290 241 227
Мин значение 1427 1003 746 635 550 478 406 367
Плотников-Зверев Среднее значение 1708 1231 904 773 655 639 511 495
Мин значение 1634 1138 820 699 578 536 440 412
Мин значение 3338 2316 1734 1420 1186 1136 929 872
Плотников-Зверев Среднее значение 4034 2890 2133 1801 1510 1448 1155 1120
Мин значение 3829 2718 2003 1648 1355 1272 998 966
Таблица 2 / Table 2
Результаты вычислительного эксперимента с загрузкой 25...30 / Results of a computational experiment with a load of 25..30
Число заданий Метод Критерий 3 4 5 6 7 8 9 10
Мин значение 1132 802 717 611 519 474 497 411
Плотников-Зверев Среднее значение 1171 894 710 616 526 502 425 412
Мин значение 1143 856 682 578 488 441 382 357
Мин значение 2035 1621 1270 1103 963 910 772 722
Плотников-Зверев Среднее значение 2165 1647 1297 1115 971 903 772 726
Мин значение 2132 1577 1261 1059 900 813 715 659
Мин значение 4847 3703 2983 2607 2248 2065 1843 1790
Плотников-Зверев Среднее значение 5133 3897 3068 2616 2245 2062 1772 1647
Мин значение 5044 3745 2974 2507 2147 1930 1648 1527
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
Таблица 3 / Table 3
Обобщенные результаты вычислительного эксперимента с загрузкой 25..30 / Generalized results of a computational
experiment with a load of 25..30
Метод Число заданий Критерий 3 4 5 6 7 8 9 10
Метод минимальных элементов 117 Среднее значение 1257 1020 847 742 679 603 578 515
Мин значение 1128 875 689 631 542 447 437 437
Плотников-Зверев Среднее значение 1166 896 703 606 528 502 430 411
Мин значение 1129 849 667 569 493 455 390 364
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 1150 859 692 584 511 475 412 393
Мин значение 1079 820 655 548 474 428 376 337
Метод минимальных элементов 217 Среднее значение 2321 1788 1498 1299 1176 1077 999 950
Мин значение 2035 1513 1254 1090 908 808 761 707
Плотников-Зверев Среднее значение 2157 1653 1295 1121 965 888 774 715
Мин значение 2094 1581 1253 1063 911 814 706 642
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 2153 1624 1286 1093 935 855 741 689
Мин значение 2035 1512 1209 1009 869 781 683 622
Метод минимальных элементов 517 Среднее значение 5471 4256 3484 3040 2691 2473 2284 2136
Мин значение 4836 3710 3021 2539 2269 2039 1827 1767
Плотников-Зверев Среднее значение 5131 3895 3071 2616 2248 2056 1774 1648
Мин значение 5029 3782 2978 2491 2140 1937 1669 1528
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 5140 3878 3097 2603 2226 1987 1746 1600
Мин значение 4836 3710 2888 2469 2055 1862 1599 1467
Таблица 4 / Table 4
Обобщенные результаты вычислительного эксперимента с загрузкой 10...50 / Generalized results of a computational
experiment with a load of 10...50
Метод Число заданий Критерий 3 4 5 6 7 8 9 10
Метод минимальных элементов 117 Среднее значение 882 662 491 415 356 344 295 284
Мин значение 753 554 397 363 290 276 215 207
Плотников-Зверев Среднее значение 906 672 494 435 361 351 297 290
Мин значение 829 619 449 375 327 278 257 230
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 882 662 491 416 356 344 295 285
Мин значение 752 553 397 363 290 276 215 207
Метод минимальных элементов 217 Среднее значение 1597 1146 869 732 619 594 488 471
Мин значение 1373 1010 736 599 528 493 397 377
Плотников-Зверев Среднее значение 1702 1224 911 779 656 631 516 495
Мин значение 1569 1116 840 682 575 535 451 407
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 1596 1145 870 731 619 594 486 471
Мин значение 1373 966 733 599 516 474 397 377
Метод минимальных элементов 517 Среднее значение 3730 2625 1966 1646 1382 1299 1075 1022
Мин значение 3389 2279 1727 1439 1176 1116 918 881
Плотников-Зверев Среднее значение 4035 2884 2131 1797 1501 1446 1155 1117
Мин значение 3805 2649 1971 1661 1343 1277 1043 952
Модификация алгоритма Плотникова-Зверева с критерием по средним элементам с быстрой остановкой Среднее значение 3732 2624 1972 1645 1376 1298 1072 1022
Мин значение 3389 2279 1727 1433 1176 1125 934 851
ISSN 1560-3644 IZVESTIYA VUZOV. SEVERO-KAVKAZSKIYREGION. TECHNICAL SCIENCE. 2020. No 2
Заключение
Как видно из вычислительного эксперимента, предложенная авторами модификация в подавляющем большинстве случаев как по минимальному, так и по среднему значению приводит к решению, гораздо более близкому к оптимальному (выделено жирным шрифтом в таблицах).
References
Поступила в редакцию /Received 23 марта 2020 г. /March 23, 2020
