Задача визначення максимально пізнього моменту початку виконання завдань із спільним жорстким директивним терміном паралельними пристроями різної продуктивності
Анотація
В статті досліджені властивості задачі календарного планування виконання завдань зі спільним жорстким директивним терміном паралельними пристроями різної продуктивності з метою максимізації моменту запуску пристроїв за умови, що усі завдання не запізнюються. Сформульована допоміжна оптимізаційна задача, за результатами якої визначені достатні умови оптимальності розкладів. На основі достатніх умов оптимальності визначено множину перестановок, які дозволяють послідовно покращувати значення критерію. Розроблена поліноміальна складова ПДС-алгоритма розв’язання задачі.
Посилання
Павлов О.А., Жданова О.Г., Сперкач М.О. Задача составления допустимого расписания с
максимально поздним моментом запуска выполнения идентичными параллельными прибо-
рами работ с общим директивным сроком / О.А. Павлов, М.О. Сперкач, О.Г. Жданова //
Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.:
“ВЕК+”, 2014. – №61 – С.93-102.
Згуровский, М. З. Принятие решений в сетевых системах с ограниченными ресурсами
[Текст]: монография / М. З. Згуровский, А. А. Павлов. – К.: Наукова думка, 2010.– 573 с.
