ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ДВУХСТАДИЙНОЙ СИСТЕМЫ ОБСЛУЖИВАНИЯ ТИПА 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.
Рецензия
Просмотров: 745
Послать статью по эл. почте 