SOLVING A TWO-MASHINE BLOCKING FLOWSHOP SCHEDULING PROBLEM WITH DUE DATES
Abstract
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.
About the Authors
V. I. Sarvanov
Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
A. V. Yafimau
EPAM Systems, FLLC, Minsk
Belarus
Belarus
References
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.
Review
Views: 744
Email this article 