节点文献
转盘上的流水作业问题
The Scheduling Problem of Flow Shops with a Transportation Turntable
【摘要】 讨论转盘上的流水作业问题,其中每个加工工件从一个工序到下一个工序需要用此转盘来运输,而且从入口到第一个加工机器和从最后一个加工机器返回工件入口,也要用此转盘来运输.在本文中,我们证明,即使只有一台加工机器,带有转盘的流水作业的加工全长问题也是强NP困难的.
【Abstract】 This paper deals with the makespan problem of flow shops with a transportation turntable,which is used for moving the jobs from any machine to the next machine,for moving the jobs from the entrance to the first machine,and for moving the jobs from the last machine to the entrance back as well.It is proved that the problem is strangly NP hard even if there is only one machine for processing. The result is obtained by using a reduction from the 3 Partition problem.
【关键词】 流水作业;
运输转盘;
加工全长;
NP困难;
三元划分;
【Key words】 flow shop; transportation turntable; makespan; NP hard; 3 partition;
【Key words】 flow shop; transportation turntable; makespan; NP hard; 3 partition;
【基金】 国家自然科学基金
- 【文献出处】 华东交通大学学报 ,JOURNAL OF EAST CHINA JIAOTONG UNIVERSITY , 编辑部邮箱 ,1997年02期
- 【分类号】O224
- 【被引频次】5
- 【下载频次】15