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

Анотація

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