On Eulerian extensions and their application to no-wait flowshop scheduling
On Eulerian extensions and their application to no-wait flowshop scheduling
复制标题
欧拉扩展及其在无等待流水作业调度中的应用
DOI：
10.1007/s10951-011-0241-1
复制
发表时间：
--
影响因子：
2
通讯作者：
N. Megow.
中科院分区：
文献类型：
--
作者：
W. Höhn;T. Jacobs;N. Megow.
我们考虑了一种由多阶段生产过程中的连铸驱动的无等待流程车间调度。任务是找到一个具有最小中断次数的可行计划，即在最后一个生产阶段连续空闲时间间隔。基于对苏勒尔扩展问题的解释，我们完全解决了任何特定情况下问题的复杂性状态：我们给出了一个非常直观的在两个加工阶段调度的最优算法，并且我们证明了所有其他问题变体都是强NP-hard的。我们还讨论了与空闲时间相关的备选调度模型及其在考虑的钢铁制造环境中的合理性。这里，我们推导常数因子近似。
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 ofinterruptions, i.e., continuous idle time intervals on the last production stage. Based on an interpretation asEulerian 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.
登录
查看更多内容
无等待车间调度的近似性和非近似性结果
DOI：
10.1109/sfcs.2000.892071
发表时间：
2000
期刊：
Proceedings 41st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Sviridenko;G. Woeginger
通讯作者：
G. Woeginger
新的多项式可解类和旅行商问题及其泛化的新启发式
DOI：
10.1016/s0166-218x(01)00271-2
发表时间：
2002
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
S. Kabadi
通讯作者：
S. Kabadi
权重为 0 和 1 的最大 ATSP 的 3/4 近似算法
DOI：
10.1007/978-3-540-27821-4_6
发表时间：
2004
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
M. Bläser
通讯作者：
M. Bläser
简化开放式流水车间紧凑调度的 NP 难度
DOI：
10.1016/s0377-2217(00)00022-9
发表时间：
2001
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
K. Giaro
通讯作者：
K. Giaro
影响因子：
2.1
作者：
C. S. Orloff
通讯作者：
C. S. Orloff