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

• Дата: 2014
• Автори: Павлов, Олександр Анатолійович, Жданова, Олена Григорівна, Сперкач, Майя Олегівна
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Kamianets-Podilskyi National Ivan Ohiienko University 2014
• Теми: календарне планування; розклад; паралельні прилади; спільний директивний термін; мінімізація максимуму відхилень від директивного терміну; ПДС-алгоритм.
• Онлайн доступ: http://mcm-tech.kpnu.edu.ua/article/view/37710
• Назва журналу: Mathematical and computer modelling. Series: Technical sciences

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