DOI: https://doi.org/10.32626/2308-5916.2014-10.148-158

Задача складання розкладу виконання завдань паралельними приладами з метою мінімізації максимуму відхилення від директивного терміну моментів завершення приладами усіх завдань

Олександр Анатолійович Павлов, Олена Григорівна Жданова, Майя Олегівна Сперкач

Анотація


Розглянута задача теорії розкладів, в якій необхідно скласти розклад виконання завдань із загальним директивним терміном ідентичними паралельними приладами за критерієм мінімізації максимального відхилення від директивного терміну моментів завершення приладами усіх завдань. Застосовуючи методологію побудови ПДС-алгоритмів, розроблено ознаки оптимальності розкладів та на їх основі визначена множина перестановок, які дозволяють послідовно покращувати значення критерію. Розроблено ПДС-алгоритм розв’язання задачі, який має наступні властивості: поліноміальна складова алгоритму (ознаки оптимальності і поліноміальний алгоритм, що їх перевіряє) одночасно є поліноміальною апроксимацією експоненціальної складової ПДС-алгоритму.


Ключові слова


календарне планування; розклад; паралельні прилади; спільний директивний термін; мінімізація максимуму відхилень від директивного терміну; ПДС-алгоритм.

Повний текст:

PDF

Посилання


Згуровский М. З. Принятие решений в сетевых системах с ограниченными ресурсами : монография / М. З. Згуровский, А. А. Павлов. — К. : Наукова думка, 2010. — 573 с.

Павлов А. А. Исследование свойств задачи календарного планирования выполнения заданий с общим директивным сроком параллельными при-борами по разным критериям оптимальности / А. А. Павлов, Е. Б. Мисю-ра, М.О. Сперкач // Вісник НТУУ «КПІ». Серія «Інформатика, управління та обчислювальна техніка». — К. : ВЕК+, 2012. — №57. — С. 15–17.

Pavlov A. A. About one subclass of polynomially solvable problems from class «Sequencing jobs to minimize total weighted completion time subject to precedence constraints» / A. A. Pavlov, L. A. Pavlova. — Uzhhorod : Karpat-skij region, 1998. — № 15. — 320 p.

Павлов А. А. Субоптимальный полиномиальный алгоритм решения одно-го класса многоэтапных сетевых задач календарного планирования / А. А. Пав¬лов, М. О. Сперкач, Е. А. Халус // Вісник НТУУ «КПІ». Серія «Інформатика, уп¬равління та обчислювальна техніка». — К. : ВЕК+, 2012. — № 57. — С. 51–55.

Поліноміальна складова ПДС-алгоритму розв’язання однієї задачі теорії розкладів / О. А. Павлов, О. Г. Жданова, О. Б. Місюра, М. О. Сперкач // Технологический аудит и резервы производства. — 2013. — №6/3 (14). — С. 47–52.

Павлов А. А. Признаки оптимальности допустимых решений трудноре-шаемых задач комбинаторной оптимизации / А. А. Павлов // Вісник НТУУ «КПІ». Серія «Інформатика, управління та обчислювальна техніка». — К. : ВЕК+, 2013. — № 59. — (подано до друку).