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

Згуровський М.З., Павлов О.А., Місюра О.Б.

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


Завантажити (pdf)