ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ДВУХСТАДИЙНОЙ СИСТЕМЫ ОБСЛУЖИВАНИЯ ТИПА FLOWSHOP С БЛОКИРОВКАМИ
Анатацыя
Рассматривается система обслуживания, в которой множество требований N = N1UN2, N1∩N2 = Ø, обслуживается на приборах M1 и M2. Особенность системы состоит в том, что время обслуживания требования из N1(N2) прибором M2(M1) равно нулю и при этом занятый прибор M1 блокирует доступ к прибору M2, а занятый прибор M2 блокирует выход обслуженных требований из системы. Исследуется задача построения расписания, при котором каждое требование из N1 (N2) покидает систему не позже заданного директивного срока D1 (D2). Доказано, что эта задача является NP-трудной и предложен псевдополиномиальный алгоритм ее решения.
Аб аўтарах
В. Сарванов
Институт математики Национальной академии наук Беларуси, Минск
Беларусь
Беларусь
О. Ефимов
EPAM Systems, ИООО, Минск
Беларусь
Беларусь
Спіс літаратуры
1. Танаев, В. С. Теория расписаний. Многостадийные системы / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич. – М.: Наука, 1989.
2. Ronconi, D. P. A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking / D. P. Ronconi // Annals of Operations Research. – 2005. – n 138. – P. 53–65.
3. Танаев, В. С. Теория расписаний. Групповые технологии / В. С. Танаев, М. Я. Ковалев, Я. М. Шафранский. – Минск: ОИПИ НАН Беларуси, 1998.
##reviewer.review.form##
Праглядаў: 746
Паслаць артыкул па эл. пошце 