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

Abstract

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

The scheduling problem is considered in which is necessary to schedule the jobs with a common due date on identical parallel machines with the criterion of minimizing the maximum deviation of the times when the machines complete all the jobs from the due date. Applying the methodology of the PDCalgorithms on their basis a set of permutations is defined that allows to consistently improve the criterion value. The PDC-algorithm for the problem solution is developed that has the following properties: the polynomial component of the algorithm (the signs of optimality and the polynomial algorithm that is checking them) is in the same time the polynomial approximation of the exponential component of the PDC-algorithm.