ПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ДВУХСТАДИЙНОЙ СИСТЕМЫ ОБСЛУЖИВАНИЯ ТИПА 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.


Дополнительные файлы

Просмотров: 132

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)