带等时空载返程运输的双机Flowshop调度问题复杂性

发布时间：2017-09-19 01:19

  本文关键词：带等时空载返程运输的双机Flowshop调度问题复杂性

  更多相关文章： Flow-shop问题 空载返程运输 调度 复杂性

【摘要】：流水作业(Flow shop)问题是调度算法研究中经典问题模型之一,有两台处理机和一台运输机且运输机每次只运输一个工件的流水作业调度问题模型在现实中有着广泛的应用。同时考虑运输机去程(从机器M1到M2)与返程(从机器M2到M1)时间,在假定运输机去程运输时间及返程空载时间相等的情况下,通过把一个强NP-complete问题——3-PARTITION问题归约成一个研究问题的实例,来证明对这个问题求解是强NP-hard的。
【作者单位】： 大连理工大学软件学院;大连东软信息学院软件工程系;
【关键词】： Flow-shop问题 空载返程运输 调度 复杂性
【基金】：国家自然科学基金项目:在线背包问题的相关模型和算法分析(11101065)资助
【分类号】：TB497;TP301.6
【正文快照】： 1引言流水作业(Flow shop)问题是调度算法研究中经典问题模型之一,是指一个包含了多台机器,多个待加工的工件需要在这些机器上依次加工的生产系统。一个标准的流水线调度问题是不计运输时间的,任务可以在被处理完之后立即移动到另一台机器上,其数学模型可表述为:给定m(m≥2)台

【参考文献】

中国期刊全文数据库 前10条

1 陈可嘉;王潇;;机器具有不可用时间间隔的两机流水车间调度问题求解性质[J];南京理工大学学报;2015年02期

2 张翠林;王烁;王军强;;考虑约束松弛的柔性流水调度研究[J];机械设计与制造工程;2014年05期

3 李小缤;白焰;耿林霄;;求解置换流水车间调度问题的改进遗传算法[J];计算机应用;2013年12期

4 刘莹;谷文祥;李向涛;;置换流水线车间调度问题的研究[J];计算机科学;2013年11期

5 陈可嘉;王潇;;两机无等待流水车间调度问题的性质[J];控制与决策;2013年10期

6 陈成栋;陈华平;朱颀;李小林;;两阶段流水车间批调度问题的蚁群优化算法[J];计算机工程;2012年19期

7 杨柳;胡志刚;龙军;;流水作业批调度问题优化算法研究[J];小型微型计算机系统;2012年06期

8 陈伯龙;;带运输时间和一个不可用约束的两台平行机排序[J];兰州大学学报(自然科学版);2009年04期

9 时凌;文军;;带运输时间和自动机的流水作业排序问题的复杂性[J];数学物理学报;2008年05期

10 刘延风;刘三阳;;置换流水车间调度的蚁群优化算法[J];计算机应用;2008年02期

【共引文献】

中国期刊全文数据库 前10条

1 兰艳;张明会;武宗涛;韩鑫;;带等时空载返程运输的双机Flowshop调度问题复杂性[J];计算机科学;2016年09期

2 马yN航;陶文华;刘阳;;基于双模式PSO算法求解置换流水车间调度问题[J];电子设计工程;2016年15期

3 程子安;童鹰;申丽娟;于帅帅;李明;;双种群混合遗传算法求解柔性作业车间调度问题[J];计算机工程与设计;2016年06期

4 林刚;刘建军;陈庆新;毛宁;;可重入流水车间类型模具热处理生产动态批调度[J];计算机集成制造系统;2016年04期

5 苏志雄;伊俊敏;;求解置换流水车间调度问题的Memetic算法[J];厦门理工学院学报;2015年06期

6 左益;公茂果;曾久琳;焦李成;;混合多目标算法用于柔性作业车间调度问题[J];计算机科学;2015年09期

7 徐杨丽;叶春明;;布谷鸟算法求解置换流水车间调度问题[J];数学理论与应用;2015年03期

8 徐杨丽;叶春明;;改进的布谷鸟算法求解置换流水车间调度问题[J];物流科技;2015年06期

9 晏晓辉;张智聪;郭建文;赵少勇;;基于HABCC的置换流水车间调度优化[J];制造业自动化;2015年11期

10 刘祚时;马力;罗金平;;混合流水车间多目标调度的小生境粒子群算法[J];机械设计与制造;2015年04期

【二级参考文献】

中国期刊全文数据库 前10条

1 顾文斌;唐敦兵;郑X;白帅福;裴文祥;;基于激素调节机制改进型自适应粒子群算法在置换流水车间调度中的应用研究[J];机械工程学报;2012年14期

2 王柏琳;李铁克;;等待时间受限的置换流水车间调度启发式算法[J];管理科学学报;2012年06期

3 刘长平;叶春明;;置换流水车间调度问题的萤火虫算法求解[J];工业工程与管理;2012年03期

4 魏麒;蒋义伟;;一类两阶段杂交流水作业的近似算法(英文)[J];软件学报;2012年05期

5 唐海波;叶春明;刘长平;柯军;;基于知识进化粒子群算法的模糊交货期流水车间调度问题[J];计算机集成制造系统;2012年04期

6 张其亮;陈永生;韩斌;;改进的粒子群算法求解置换流水车间调度问题[J];计算机应用;2012年04期

7 陆超;王丽亚;;双机无等待流水作业调度算法研究[J];工业工程与管理;2012年01期

8 李铁克;王柏琳;;等待时间受限的两阶段流水车间调度问题性质研究[J];管理工程学报;2011年01期

9 黄英杰;姚锡凡;颜亮;余铭奇;;基于目标级联法的作业车间调度[J];华南理工大学学报(自然科学版);2010年06期

10 王炳飞;王劲林;刘学;刘磊;;蚁群算法在服务器集群批量任务调度中的应用[J];小型微型计算机系统;2010年04期

【相似文献】

中国期刊全文数据库 前10条

1 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期

2 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

3 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期

4 席裕庚,王长军;控制、规划和调度问题中的博弈论应用[J];中国计量学院学报;2005年01期

5 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期

6 喻道远;史登松;刘盛强;张三强;;带模糊排序的移动瓶颈法求解不确定调度问题[J];机械制造;2011年02期

7 刘鹏;周晓晔;衣娜;;带有减少线性恶化效应的双代理调度问题[J];系统工程学报;2011年03期

8 刘晓东;陈英武;龙运军;贺仁杰;李菊芳;;同型机在线调度问题研究进展[J];计算机集成制造系统;2012年03期

9 姚君遗，杨善林，，左春荣;基于实例FMS的AGV调度数学模型与算法[J];合肥工业大学学报(自然科学版);1995年01期

10 董平;机器调度问题及求解方法[J];物流技术与应用;1997年01期

中国重要会议论文全文数据库 前10条

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

中国重要报纸全文数据库 前2条

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

中国博士学位论文全文数据库 前10条

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 李雪松;模糊环境下若干单机批加工调度问题的模型及其算法研究[D];哈尔滨工业大学;2015年

4 汤雅连;关联物流运输调度问题研究[D];广东工业大学;2015年

5 周理;高效可重构阵列计算：体系结构，设计方法与程序映射技术研究[D];国防科学技术大学;2014年

6 冯大光;一类批处理机调度的理论和方法研究[D];东北大学;2011年

7 孟盈;钢铁企业并行批生产决策与调度问题研究[D];东北大学;2011年

8 杨磊;内容网络中内容调度技术研究[D];重庆大学;2015年

9 李亚志;流水制造单元调度智能优化方法[D];东南大学;2015年

10 丁宁;若干调度问题的算法研究[D];大连理工大学;2016年

中国硕士学位论文全文数据库 前10条

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 吉佳红;基于细菌觅食算法的改进及应用研究[D];江苏科技大学;2015年

9 周超;柔性作业车间批量问题研究[D];宁波大学;2014年

10 赵兴野;工序顺序柔性作业车间描述与调度研究[D];大连理工大学;2015年

本文编号：878638