基于改进拉格朗日松弛的零等待混合流水车间调度研究

发布时间：2017-05-03 14:01

  本文关键词：基于改进拉格朗日松弛的零等待混合流水车间调度研究，，由笔耕文化传播整理发布。

【摘要】：混合流水车间(HFS)调度是一个复杂的生产决策过程,在玻璃、钢铁等现实工业中均可提炼出HFS结构。HFS调度问题是一般的流水车间调度问题的推广,其特点是在整个加工阶段中,至少有一个加工阶段存在并行机。在实际的HFS系统中,调度往往受到机器能力、生产时间等资源的约束限制,因此,在现有的资源条件下,如何科学合理分配各项资源就显得尤为重要。针对HFS调度的研究现状,本文重点研究了带释放时间的零等待HFS调度和带截止时间的动态零等待HFS调度问题。针对带释放时间的零等待HFS调度问题,考虑工件动态到达的约束限制,调度目标是最小化总加权完成时间,建立静态离散时间的整数规划模型,设计了一种基于代理次梯度算法的改进拉格朗日松弛算法求解。采用基于工件分解的策略将拉格朗日松弛问题分解为多个容易求解的工件级子问题,然后通过每次迭代最优求解所有子问题中的某几个得到松弛问题的近似解,进而获得更好的搜索拉格朗日乘子的代理次梯度方向,由于所得到的解往往是不可行的,因此通过设计一个两阶段的启发式来构造可行解。通过进行大量的实验仿真,证明了基于代理次梯度算法的拉格朗日松弛算法具有很强的可行性和优越性,对决策者安排生产具有较高的指导价值。在带释放时间的零等待HFS调度问题研究的基础上,增加了截止时间约束,对带截止时间的零等待HFS调度问题进行研究,用相同的方法建立数学模型,依然使用基于代理次梯度算法的拉格朗日松弛算法求解。通过仿真实验,证明了所设计的算法在求解带截止时间的零等待HFS调度问题时依然拥有较大的优势。
【关键词】：零等待混合流水车间 释放时间 截止时间 拉格朗日松弛 代理次梯度
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497
【目录】：

• 摘要4-5
• Abstract5-10
• 1 绪论10-15
• 1.1 研究背景10-11
• 1.2 研究意义11-12
• 1.3 本文的研究路线及主要工作12-15
• 1.3.1 本文的研究路线12-13
• 1.3.2 本文的主要工作13-15
• 2 相关理论研究综述15-29
• 2.1 零等待HFS调度及LR算法理论15-20
• 2.1.1 零等待HFS调度理论15-16
• 2.1.2 LR算法理论16-20
• 2.2 零等待HFS调度问题研究综述20-24
• 2.2.1 HFS调度问题20-22
• 2.2.2 零等待HFS调度问题22-24
• 2.3 HFS调度问题优化方法研究综述24-28
• 2.3.1 精确求解算法24-25
• 2.3.2 近似求解算法25-28
• 2.4 本章小结28-29
• 3 零等待HFS调度模型的建立29-34
• 3.1 问题描述29-31
• 3.2 模型的建立31-33
• 3.2.1 符号定义31-32
• 3.2.2 模型32-33
• 3.3 本章小结33-34
• 4 基于SSG的LR算法求解动态零等待HFS调度问题34-44
• 4.1 动态HFS调度数学描述34-36
• 4.1.1 研究现状34-36
• 4.1.2 建立模型36
• 4.2 拉格朗日松弛算法36-39
• 4.2.1 基于工件的分解策略36-37
• 4.2.2 求解工件级子问题37
• 4.2.3 更新拉格朗日乘子37-38
• 4.2.4 构造可行解38-39
• 4.3 仿真实验39-43
• 4.3.1 参数设置及实验39-42
• 4.3.2 实验结果分析42-43
• 4.4 本章小结43-44
• 5 基于SSG的LR算法求解带截止时间的动态零等待HFS调度44-49
• 5.1 带截止时间的动态零等待HFS调度数学描述44-45
• 5.1.1 研究现状44-45
• 5.1.2 建立模型45
• 5.2 拉格朗日松弛算法45
• 5.3 仿真实验45-48
• 5.3.1 参数设置及实验45-47
• 5.3.2 实验结果分析47-48
• 5.4 本章小结48-49
• 6 总结与展望49-51
• 6.1 本文总结49-50
• 6.2 展望50-51
• 参考文献51-56
• 致谢56-57
• 个人简历、在学期间发表的学术论文与研究成果57

【参考文献】

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

1 于艳辉;李铁克;;一类缓冲区有限的两阶段混合流水车间调度问题及算法[J];工业工程;2013年04期

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

3 轩华;唐立新;;实时无等待HFS调度的一种拉格朗日松弛算法[J];控制与决策;2006年04期

4 王圣尧;王凌;许烨;周刚;;求解混合流水车间调度问题的分布估计算法[J];自动化学报;2012年03期

5 张其亮;陈永生;;求解双向无等待混合流水车间调度问题的粒子群优化算法[J];计算机集成制造系统;2013年10期

6 何龙敏;孙世杰;程明宝;;A two-stage flexible flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage[J];Journal of Harbin Institute of Technology;2008年05期

7 轩华;;运输能力有限混合流水车间调度的改进拉格朗日松弛算法[J];计算机集成制造系统;2013年07期

8 刘志新,谢金星,李建国,董杰方;A Heuristic for Two-Stage No-Wait Hybrid Flowshop Scheduling with a Single Machine in Either Stage[J];Tsinghua Science and Technology;2003年01期

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

1 康宁;航天测控优化调度模型及其拉格朗日松弛求解算法[D];国防科学技术大学;2011年

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

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

1 陶继平;基于拉格朗日松弛法的调度算法研究[D];上海交通大学;2014年

  本文关键词：基于改进拉格朗日松弛的零等待混合流水车间调度研究，由笔耕文化传播整理发布。

本文编号：343114