Полiномiальнi алгоритми розв’язування деяких задач побудови розкладiв приладу для заявок з очiкуванням - Ємець, О.О.; Леонова, М.В. (Доповіді НАН України, 2016)
Стаття присвячена розробцi класифiкацiї задач Z = (P,R,W, F) знаходження розкладу роботи одного приладу iз заданими параметрами. Кожне з завдань має додатну вагу wi ∈ W, час обробки pi ∈ P та час очiкування ri ∈ R, коли воно недоступне для обслуговування, а також заданий критерiй F оптимальностi розкладу. Показана можливiсть полiномiального за часом знаходження розкладiв цих задач. Доведено, що оптимальним розв’язком задач знаходження розкладу роботи одного приладу є упорядкування σ = (i₁, . . . ., ik) завдань згiдно з упорядкуванням по неспаданню елементiв перестановок X = (ri₁, . . . ., rik ) ∈ Ekn(R), де R— мультимножина часiв очiкування завдань.