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

  Повний текст PDF - 425.802 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"