有模具限制的并行机台调度问题研究

发布时间：2017-11-01 10:14

  本文关键词：有模具限制的并行机台调度问题研究

  更多相关文章： 并行机器 最大完工时间 模具限制 启发式算法

【摘要】：在基于工业4.0概念下的智能制造领域,车间调度问题的研究愈加受到制造企业的关注。特别是在科技含量高、自动化程度明显的生产车间中,针对制造过程的优化是提高生产效率、减少成本和保证产能的重要手段。随着生产方式的不断改进,基于现实生产中的约束提出的调度问题更加贴近生产实际情况,对于此类问题的研究为企业在生产调度和排程方面提供了可靠依据和参考。本文主要研究了有模具限制的等效并行机器最小化最大完工时间问题。在半导体车间中,晶圆曝光操作需要在特殊的并行设备上通过光罩辅助加工,光罩需要与晶圆对应使用且数量较少。在这样的情况下,制造者需要对晶圆的加工顺序做出合理安排,优化生产流程,提高机器的利用率,达到最小化最大完工时间的目的。并行机(Parallel Machine)调度问题的研究在理论和实际中都具有重要意义。在理论研究方面,并行机调度问题不仅是单机问题的衍生问题,也是混合流水车间问题的特殊情况;在实际生产方面,并行机调度问题频繁出现在工业流程中,同时其研究方法在多阶段系统的分解程序中也具有广泛应用。等效并行机器最小化最大完工时间问题可以表示为maxP||C,在无任何约束的情况下,即使是在两台并行机器的生产环境中,也已经被证明为NP-hard问题。首先,本文针对有模具限制的并行机器调度问题,建立了包含工件位置约束和加工条件约束的数学模型,初步得到小规模问题中的最优解。此外,通过对问题约束的简化,在maxP||C问题的数学模型基础上,得到了问题下界的计算方法;其次,在对问题特点的分析及归纳的基础上,提出了两种启发式演算法,试图通过这两种方式达到高效解决大规模问题的目的,两种启发式演算法具有各自的特点。第一,通过数学证明的方法,提出了两种算法的worst case,得到了两种启发式演算法得到的解与最优解之间的差距估计。第二,针对算法的伪代码进行了分析和计算,得到了两种算法的复杂度,对算法的性能及求解效率做出了比较;最后,为了证明所提出的两种启发式演算法的求解效果,对离散的粒子群优化算法以及变领域优化算法做出了改进。一是提出了更加适合题目类型的编码方式,对于粒子群优化算法采用多维度的二进制编码方式,迭代更新时保留了局部最优序列的特点。二是初始解的产生方式采用了所提出的两种启发式算法,这种初始解的产生方式使算法在较短的时间内就可以取得较优的解。实验分析证明:提出的两种启发式算法DMLPT和TLPT以及改进的两种万用启发式算法可以得到问题的较优解。尤其对于两种启发式算法DMLPT和TLPT算法的比较分析中发现,两种算法的求解效率和质量具有较大优势,其中DMLPT算法在大规模问题中表现出求解时间短、与最优解差距小等特点。
【关键词】：并行机器 最大完工时间 模具限制 启发式算法
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TB497
【目录】：

• 摘要4-6
• Abstract6-10
• 第一章 绪论10-20
• 1.1 研究背景及意义10-12
• 1.2 国内外研究现状12-16
• 1.2.1 国外研究现状12-14
• 1.2.2 国内研究现状14-16
• 1.3 主要的研究内容及结构安排16-20
• 1.3.1 主要研究内容16-18
• 1.3.2 本文的结构安排18-20
• 第二章 数学模型与启发式算法20-42
• 2.1 问题的背景与描述20-22
• 2.2 混合整数规划模型的建立22-27
• 2.2.1 符号及变量的定义22-23
• 2.2.2 数学模型的建立23-27
• 2.3 启发式算法建立及分析比较27-40
• 2.3.1 LPT规则概述27-29
• 2.3.2 TLPT算法的建立29-32
• 2.3.3 TLPT算法的性能分析32-35
• 2.3.4 DMLPT算法的建立35-38
• 2.3.5 DMLPT算法的性能分析38-40
• 2.4 本章小结40-42
• 第三章 万用启发式演算法的设计42-60
• 3.1 万用启发式算法概述42-44
• 3.2 粒子群优化算法44-52
• 3.2.1 粒子群优化算法的原理44-48
• 3.2.2 改进的离散粒子群算法的建立48-52
• 3.3 变邻域搜索算法52-58
• 3.3.1 变邻域搜索算法的原理52-55
• 3.3.2 改进的变邻域搜索算法的建立55-58
• 3.4 本章小结58-60
• 第四章 实验分析及应用实例60-74
• 4.1 实验的目的及应用背景60-61
• 4.2 实验的环境及参数设置61-62
• 4.3 实验的结果及对比分析62-72
• 4.4 本章小结72-74
• 第五章 结论与展望74-76
• 5.1 全文结论74-75
• 5.2 未来展望75-76
• 参考文献76-82
• 作者简介82-84
• 攻读学位期间主要从事的科研工作84-86
• 致谢86

【相似文献】

中国期刊全文数据库 前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年

，

本文编号：1126364