Минимизация лексикографического критерия для допустимого расписания на параллельных приборах с произвольными директивными сроками
Анотація
В статье разработаны ПДС-алгоритмы решения задач составления расписаний выполнения независимых
работ с директивными сроками параллельными приборами равной и разной производительности по век-
торному (лексикографическому) либо скалярному критерию максимизации минимального момента начала
работы приборов. На основе созданных ранее признаков оптимальности допустимых решений разработаны
алгоритмы, реализующие полиномиальную составляющую ПДС-алгоритма и полиномиальную аппрокси-
мацию точного алгоритма решения рассматриваемых задач – эвристические или приближенные алгоритмы
с оценкой отклонения от оптимального решения.
Посилання
Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ресурсами: Мо-
нография.– К.: Наукова думка. – 2010. – 573 с.
Конструктивные полиномиальные алгоритмы решения индивидуальных задач из класса NP /
А.А.Павлов, А.Б.Литвин, Е.Б.Мисюра, Л.А.Павлова, В.И.Родионов, под редакцией А.А.Павлова.– К.:
Техника, 1993.– 126 с.
Pavlov A., Pavlova L. PDC-algorithms for intractable combinatorial problems. Theory and methodology of design.–
Uzhhorod, «Karpatskij region» shelf №15, 1998.– 320 pp.
Павлов А.А. Признаки оптимальности допустимых решений труднорешаемых задач комбинаторной оп-
тимизации // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.:
“ВЕК+”, 2013. – №59 – С.4–11.
