vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-9Research ArticleМАТЕМАТИКАMATHEMATICSПОСТРОЕНИЕ РАСПИСАНИЙ ДЛЯ ДВУХСТАДИЙНОЙ СИСТЕМЫ ОБСЛУЖИВАНИЯ ТИПА FLOWSHOP С БЛОКИРОВКАМИSOLVING A TWO-MASHINE BLOCKING FLOWSHOP SCHEDULING PROBLEM WITH DUE DATESСарвановВ. И.SarvanovV. I.sarvanov@im.bas-net.byЕфимовО. В.YafimauA. V.aleh.yafimau@gmail.comИнститут математики Национальной академии наук Беларуси, МинскInstitute of Mathematics of the National Academy of Sciences of Belarus, MinskEPAM Systems, ИООО, МинскEPAM Systems, FLLC, Minsk201614052016015768Copyright © Сарванов В.И., Ефимов О.В., 20162016Сарванов В.И., Ефимов О.В.Sarvanov V.I., Yafimau A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/9

Рассматривается система обслуживания, в которой множество требований N = N1UN2, N1∩N2 = Ø, обслуживается на приборах M1 и M2. Особенность системы состоит в том, что время обслуживания требования из N1(N2) прибором M2(M1) равно нулю и при этом занятый прибор M1 блокирует доступ к прибору M2, а занятый прибор M2 блокирует выход обслуженных требований из системы. Исследуется задача построения расписания, при котором каждое требование из N1 (N2) покидает систему не позже заданного директивного срока D1 (D2). Доказано, что эта задача является NP-трудной и предложен псевдополиномиальный алгоритм ее решения. 

This work considers solving a particular type of blocking flowshop scheduling problem. In the environment under consideration there are only two machines (denoted as M1 and M2). For each job its execution time on one of these machines equals to zero. For each job with a non-zero execution time on machine M1 (M2) there is a due date D1 (D2 respectively). The authors prove that the problem is NP-hard and propose a pseudo-polynomial time algorithm that solves it. 

система обслуживания типа flowshopблокировкапсевдополиномиальный алгоритмдинамическое программированиеNP-трудная проблемадирективные срокиflowshop schedulingblockingpseudopolynomial algorithmdynamic programmingNP-hard problemdue datesReferencesТанаев, В. С. Теория расписаний. Многостадийные системы / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич. – М.: Наука, 1989.Танаев, В. С. Теория расписаний. Многостадийные системы / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич. – М.: Наука, 1989.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.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.Танаев, В. С. Теория расписаний. Групповые технологии / В. С. Танаев, М. Я. Ковалев, Я. М. Шафранский. – Минск: ОИПИ НАН Беларуси, 1998.Танаев, В. С. Теория расписаний. Групповые технологии / В. С. Танаев, М. Я. Ковалев, Я. М. Шафранский. – Минск: ОИПИ НАН Беларуси, 1998.

The authors declare that there are no conflicts of interest present.