考虑运输时间的两台机器流水调度问题研究

发布时间：2021-03-15 13:41

　　流水调度问题是组合优化领域的经典问题之一,因为与实际生产密切相关,是目前研究较为广泛的一种调度问题。在整个生产过程中,产品的加工与产品的运输是最重要的两个环节,如果将两者结合并提出合理的解决方案,既可以节约生产成本,又可以提高生产效率。本文主要研究考虑运输时间的两台机器和一台运输机的流水调度,根据运输机所处的位置,分为两种模型。模型1:工件先在两台流水机器上加工,然后由运输机运输到目的地;模型2:工件先在一台流水机器上加工,然后由运输机运输到另一台流水机器上继续加工。本文研究了以上两种模型的计算复杂性,设计了模型1在某些特殊情况下的最优调度算法,同时改进了这两种模型近似算法的近似比,具体结果如下:首先,对于模型1,当运输机每次最多运输2个工件时,Yuan等人在2007年只证明该问题是一般NP-难。本文证明了该问题是强NP-难,解决了2007年以来一直未解的问题。对于模型2,目前其复杂性的研究结果如下:2001年Hurink和Lee等人分别证明了当运输机每次运输1个或3个及以上工件时,这两种情况都是强NP-难,而每次最多运输2个工件时,该问题是否是强NP-难十几年来尚未被证明。本文证明了... 

【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校

【文章页数】：95 页

【学位级别】：博士

【部分图文】：

图２．３大工件在机器５上加工完成时间??Ｆｉｇ．２．３?Ｃｏｍｐｌｅｔｉｎｇ?ｔｉｍｅ?ｏｆ?ｂｉｇ?ｊｏｂ?ｂ〇?ｏｎ?ｍａｃｈｉｎｅ?Ｂ??

图２．４大工件＆〇和极小工件调度示意图??Ｆｉｇ．２．４?Ｔｈｅ?ｓｃｈｅｄｕｌｅ?ｆｏｒ?ｂｉｇ?ｊｏｂ?６〇?ａｎｄ?ｔｉｎｙ?ｊｏｂ?ｔ〇??

图２．５第一个有序组调度示意图?？??Ｆｉｇ．２．５?Ｔｈｅ?ｓｃｈｅｄｕｌｅ?ｄｉａｇｒａｍ?ｏｆ?ｔｈｅ?ｆｉｒｓｔ?ｏｒｄｅｒｅｄ?ｇｒｏｕｐ??

【参考文献】：
期刊论文
[1]P/NP问题的答案是P≠NP[J]. 温邦彦.  重庆理工大学学报(自然科学版). 2010(09)
[2]生产调度研究综述[J]. 余建军,张定超,周铭新.  中国制造业信息化. 2009(17)
[3]带运输时间和自动机的流水作业排序问题的复杂性[J]. 时凌,文军.  数学物理学报. 2008(05)
[4]生产调度理论和方法研究综述[J]. 徐俊刚,戴国忠,王宏安.  计算机研究与发展. 2004(02)
[5]3机Flow-shop调度问题研究[J]. 陈雄,汤光强,吴启迪.  信息与控制. 2002(03)
[6]排序、经典排序和新型排序[J]. 唐国春.  数学理论与应用. 1999(03)

硕士论文
[1]两阶段车间作业排序问题的研究[D]. 杨佳雯.浙江理工大学 2016
[2]若干带运输排序问题研究[D]. 王学士.浙江理工大学 2015



本文编号：3084275