启发式算法求解等待时间受限的两阶段流水车间调度问题

发布时间：2018-07-09 18:09

  本文选题：调度 + 两阶段流水车间　； 参考：《管理工程学报》2014年02期

【摘要】：等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性,有必要探索问题特征来开发近似求解算法。本文分析了此问题与一般两阶段流水车间调度和无等待两阶段流水车间调度的关系,给出了两类特殊问题的多项式求解方法,探讨了最优调度的工件序列特征。在此基础上,设计了基于排列排序的启发式算法,算法应用Gilmore-Gomory启发式生成初始序列,构造调度解的可替换集合实现迭代寻优,并利用工件序列特征调整工件顺序以优化当前调度。通过对算法的求解性能进行理论分析和实验验证,进一步表明了该算法的有效性。
[Abstract]:The two-stage flow shop scheduling problem with waiting time constraints has the complexity of strong NP-hard, so it is necessary to explore the characteristics of the problem to develop approximate solution algorithm. In this paper, the relationship between this problem and general two-stage flow-shop scheduling and no-wait two-stage flow-shop scheduling is analyzed. The polynomial solution method for two special problems is given, and the sequence characteristics of the optimal scheduling are discussed. On this basis, a heuristic algorithm based on permutation ordering is designed. Gilmore-Gomory heuristic is used to generate the initial sequence, and the alternative set of scheduling solutions is constructed to achieve iterative optimization. In order to optimize the current scheduling, the sequence of jobs is adjusted by the feature of job sequence. The effectiveness of the algorithm is further demonstrated by theoretical analysis and experimental verification.
【作者单位】： 北京科技大学东凌经济管理学院;钢铁生产制造执行系统技术教育部工程研究中心;
【基金】：国家自然科学基金资助项目(70771008) 中央高校基本科研业务费专项资金资助项目(FRF-TP-12-116A) 中国博士后科学基金资助项目(2012M510324)
【分类号】：C931.6

【参考文献】

相关期刊论文 前6条

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

2 李铁克;尹兆涛;;等待时间受限的流水车间调度问题的启发式算法[J];管理学报;2009年10期

3 王晶;姚辉;王艳亮;;有限等待流水车间调度邻域搜索算法[J];工业工程与管理;2010年03期

4 尹兆涛;李铁克;肖拥军;;等待时间受限Flowshop调度的HGA算法[J];计算机工程;2009年21期

5 王秀英;柴天佑;郑秉霖;;炼钢-连铸智能调度软件的开发及应用[J];计算机集成制造系统;2006年08期

6 潘全科;赵保华;屈玉贵;;无等待流水车间调度问题的优化[J];计算机学报;2008年07期

【共引文献】

相关期刊论文 前10条

1 郑忠;刘海玉;高小强;何腊梅;张涛;陈开;;炼钢-连铸生产计划调度一体化的仿真优化模型[J];重庆大学学报;2010年03期

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

3 何建佳;徐福缘;;SDN供需流的两阶段及其优化分析——基于木地板生产企业的视角[J];中国管理信息化;2009年03期

4 王柏琳;;炼钢连铸动态调度专家系统设计与仿真[J];中国管理信息化;2009年21期

5 刘青;汪宙;常健;王彬;谢飞鸣;王宝;;炼钢厂的精细制造[J];钢铁;2013年01期

6 轩华;;带有限等待的动态HFS调度的拉格朗日松弛算法[J];工业工程与管理;2013年03期

7 薄洪光;潘裕韬;;并行流水生产线协调排产模型及应用研究[J];工业工程与管理;2013年05期

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

9 王初阳;李小平;王茜;苑迎春;;有准备时间无等待流水车间调度的搜索算法[J];计算机研究与发展;2010年04期

10 施若;宗利永;;求解无等待Job Shop调度的量子粒子群算法[J];计算机工程与应用;2010年26期

相关博士学位论文 前6条

1 宋存利;生产调度问题及其智能优化算法研究[D];大连理工大学;2011年

2 卢克斌;炼钢—连铸生产计划与调度的优化方法研究及应用[D];东北大学;2010年

3 张建明;基于改进量子进化算法的生产调度问题研究[D];华东理工大学;2013年

4 王志美;铁路网车流组织与双向编组站作业分工综合优化[D];北京交通大学;2013年

5 刘莹;智能规划与规划识别中若干重要问题的研究[D];东北师范大学;2013年

6 郭盈;实际复杂生产调度问题的新模型与算法研究[D];合肥工业大学;2012年

相关硕士学位论文 前10条

1 陈曦;ERP集成的离散制造企业MES应用研究[D];大连理工大学;2010年

2 杨新玲;基于时间D-子集任务排序与调度问题研究[D];沈阳大学;2010年

3 熊世成;铝型材生产线调度问题研究[D];中南大学;2011年

4 肖艳;基于改进的庄家法则和聚类方法的多目标遗传算法的研究与应用[D];安徽理工大学;2011年

5 刘建;炼钢厂钢包跟踪与调度研究[D];杭州电子科技大学;2010年

6 王婷;印染生产调度问题研究及其调度软件设计[D];浙江大学;2008年

7 李彪;多智能体冶铸轧调度系统的开发研究[D];内蒙古科技大学;2008年

8 肖飞;面向炼钢—连铸的元胞自动机调度模型研究[D];武汉科技大学;2008年

9 吕大光;焦炭质量预测及高炉优化模型研究[D];重庆大学;2009年

10 卢玉锋;炼钢—连铸优化排程的基础研究[D];内蒙古科技大学;2009年

【二级参考文献】

相关期刊论文 前2条

1 陶章华,李靖华,赵冬梅;有多重最优解的流水型两工序排序问题研究[J];管理工程学报;2001年01期

2 李铁克;尹兆涛;;等待时间受限的流水车间调度问题的启发式算法[J];管理学报;2009年10期

【相似文献】

相关期刊论文 前10条

1 李铁克;尹兆涛;;等待时间受限的流水车间调度问题的启发式算法[J];管理学报;2009年10期

2 刘振刚;王道平;金锋;;带组换装时间的单机调度问题[J];北京科技大学学报;2009年10期

3 孙吴胜;毛宁;陈庆新;;一种兼顾CNC与EDM加工工序的模具电极调度启发式算法[J];工业工程;2008年02期

4 杨圣祥,汪定伟;神经网络和启发式算法混合策略解Job-shop调度问题[J];系统工程学报;1999年02期

5 王韬;;半导体生产批处理调度的研究现状与对策[J];科技创新导报;2009年27期

6 黄锦钿;陈庆新;毛宁;;具有成组约束的柔性同序加工车间的排序算法[J];工业工程;2011年02期

7 唐加福;董纲;潘震东;孔媛;;免费接送机场服务的多目标规划模型及算法[J];管理科学学报;2008年06期

8 曹克官;陈峰;;多车辆直运越库调度的建模与启发式算法[J];上海交通大学学报;2009年09期

9 王建华;李南;黄贤凤;郭慧;;敏捷供应链插单调度优化的启发式算法[J];计算机应用;2010年10期

10 马东彦;;越库作业调度问题及其启发式算法研究[J];物流技术;2007年06期

相关会议论文 前10条

1 谭思彤;涂奉生;;具有准备时间的单机多类产品调度[A];1997年中国控制会议论文集[C];1997年

2 尹新;杨自厚;;带有等待时间惩罚的提前／拖期调度问题的启发式解法[A];1994中国控制与决策学术年会论文集[C];1994年

3 辛维政;董光亮;李济生;黄永宣;;多星测控调度问题的建模与仿真[A];'2008系统仿真技术及其应用学术会议论文集[C];2008年

4 陈国仁;王秀梅;杨书评;;应用于立体仓库的自动导引车(AGV)的运行优化设计[A];先进制造技术论坛暨第三届制造业自动化与信息化技术交流会论文集[C];2004年

5 刘长有;薛原;石青辉;;固定货架中大规模拣选任务的拣选路径优化[A];2003中国控制与决策学术年会论文集[C];2003年

6 刘智力;刘晓强;谢国庆;;一种启发式炼钢-连铸动态调度算法研究[A];冶金轧制过程自动化技术交流会论文集[C];2005年

7 康一梅;郑应平;;同等机器上非独立任务的调度[A];1994年中国控制会议论文集[C];1994年

8 毛建忠;吴智铭;;基于知识的柔性加工车间的调度仿真系统[A];1995中国控制与决策学术年会论文集[C];1995年

9 乔非;吴启迪;严隽薇;;基于扩展Petri网的FMS调度结构[A];1998中国控制与决策学术年会论文集[C];1998年

10 李兵;蒋慰孙;;优化调度的一种新方法[A];1995年中国控制会议论文集（下）[C];1995年

相关重要报纸文章 前10条

1 河南省邮政局公众服务处 雷俊发;改进车辆配置和调度[N];中国邮政报;2003年

2 清华大学计算机科学与技术系 经彤 洪先龙 许静宇;IC布线理论与关键技术[N];计算机世界;2005年

3 谢群;水库调度的可持续发展之路[N];中国水利报;2006年

4 本报评论员　邵颖波;民工潮应该如何调度？[N];21世纪经济报道;2006年

5 张瑛 记者 李及肃;市长王兆华检查全市棚户区拆迁 回迁工作[N];辽源日报;2007年

6 费宗莲;UTM引领安全潮流[N];计算机世界;2005年

7 学生记者 肖佳平;人生是一个不断学习的过程[N];新清华;2004年

8 阎轶洁;凌晨入住怎么收费[N];太原日报;2007年

9 ;精品ASON构建智能光传输网[N];网络世界;2006年

10 记者　 李含;在科学的殿堂中追求完美[N];新清华;2006年

相关博士学位论文 前10条

1 邓冠龙;基于元启发式算法的调度问题若干研究[D];华东理工大学;2012年

2 宋继伟;轧辊热处理过程中若干调度问题的启发式算法研究[D];东北大学;2010年

3 柳春锋;工程项目中技能型员工调度问题研究[D];合肥工业大学;2011年

4 汤健超;基于混合进化算法的若干调度问题研究[D];华南理工大学;2012年

5 黎展滔;具有成组约束的柔性流水车间作业计划制定的启发式算法[D];广东工业大学;2012年

6 孙连坤;网络化控制系统调度与控制协同设计[D];天津大学;2009年

7 杜冰;批处理机调度问题的模型与优化方法研究[D];中国科学技术大学;2011年

8 杨敬松;数字微流控生物芯片的布局及调度问题研究[D];吉林大学;2008年

9 刘志雄;调度问题中的粒子群优化方法及其应用研究[D];武汉理工大学;2005年

10 蒋淑s，

本文编号：2110230