期刊
JOURNAL OF SCHEDULING
卷 15, 期 3, 页码 295-309出版社
SPRINGER
DOI: 10.1007/s10951-011-0241-1
关键词
No-wait flowshop; Complexity; Approximation algorithms; Machine idle times; Continuous casting; Eulerian extensions
资金
- Deutsche Forschungsgemeinschaft (DFG) [1307]
- German Academic Exchange Service (DAAD)
We consider a variant of no-wait flowshop scheduling that is motivated by continuous casting in the multistage production process in steel manufacturing. The task is to find a feasible schedule with a minimum number of interruptions, i.e., continuous idle time intervals on the last production stage. Based on an interpretation as Eulerian Extension Problems, we fully settle the complexity status of any particular problem case: We give a very intuitive optimal algorithm for scheduling on two processing stages with one machine in the first stage, and we show that all other problem variants are strongly NP-hard. We also discuss alternative idle time related scheduling models and their justification in the considered steel manufacturing environment. Here, we derive constant factor approximations.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据