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

• Date: 2014
• Main Authors: Павлов, Олександр Анатолійович, Жданова, Олена Григорівна, Сперкач, Майя Олегівна
• Format: Article
• Language: Ukrainian
• Published: Kamianets-Podilskyi National Ivan Ohiienko University 2014
• Subjects: календарне планування; розклад; паралельні прилади; спільний директивний термін; мінімізація максимуму відхилень від директивного терміну; ПДС-алгоритм.
• Online Access: http://mcm-tech.kpnu.edu.ua/article/view/37710
• Journal Title: Mathematical and computer modelling. Series: Technical sciences

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