Поліноміальні алгоритми розв’язування деяких задач побудови розкладів приладу для заявок з очікуванням

Анотація

Стаття присвячена розробці класифікації задач Z=(P,R,W,F) знаходження розкладу роботи одного приладу із заданими параметрами. Кожне з завдань має додатну вагу w_i∈W, час обробки p_i∈P та час очікування r_i∈R, коли воно недоступне для обслуговування, а також заданий критерій F оптимальності розкладу. Показана можливість поліноміального за часом знаходження розкладів цих задач. Доведено, що оптимальним розв’язком задач знаходження розкладу роботи одного приладу є упорядкування σ=(i₁,…,i_k) завдань згідно з упорядкуванням по неспаданню елементів перестановок X=(r_i1,…,r_ik)∈E_kn(R), де R — мультимножина часів очікування завдань.