基于列生成算法的柔性车间调度研究

发布时间：2021-01-08 18:23

　　柔性车间调度问题的研究大多集中在近似算法,如启发式算法、人工智能算法等。尤其是带有无等待约束的柔性车间调度问题,由于问题的复杂性,很难找到一种精确算法在较短时间内有效求解。本研究介绍一种求解柔性流水车间调度模型的思路,重点关注两类柔性车间调度问题:柔性作业车间和柔性开放车间,针对每类问题的特殊性质,设计基于列生成（CG）的精确算法,有一定的实际生产指导意义。首先对问题进行数学描述,建立混合整数规划模型。柔性车间调度问题属于复杂的大规模排序问题,即使对于小规模的问题也是NP难的。基于列生成算法思想,建立每类车间调度的集合划分模型,包括一个限制性主问题和一个价格子问题。设计了特定的动态规划算法求解价格子问题,并用改进的分支定界算法寻找整数最优解。对于柔性流水车间（FFS）,分析了均衡流水车间（PFS）问题的最优化策略,其中求解价格子问题的动态规划迭代过程和求解最优整数解的分支定界策略都是基于该问题本身的特性,即基于作业完工时间（completion time）的。对于柔性作业车间（FJS）和柔性开放车间（FOS）,考虑了一种两阶段带有无等待约束的均衡车间,由于问题的特殊性,用基于作业对的策... 

【文章来源】：浙江工业大学浙江省

【文章页数】：74 页

【学位级别】：硕士

【部分图文】：

s-t最短路径性质2-1假设s到t的最短路径经过节点p，那么子路径(s,p)及(p,t)分别是从s到p

第 3 章 柔性流水车间调度问题 3,1,2,4,5,6,7,8,9 ，此时的目标函数值为 221520。第二步，调整作业 5，得到的新的作业排序为 3,5,1,2,4,6,7,8,9 ，此时的目标函数值为 220040。第三步，调整作业 8，得到新的作业排序为 3,5,8,1,2,4,6,7,9 ，此时的目标函数值为 219240。第四步，调整作业 6，得到新的作业排序为 3,5,8,1,6,2,4,7,9 ，此时的目标函数值为 219110。此时通过互换操作得到 PFS 问题的一个最优排序。图 3-2 表示该例子的最终排序方案。

第 3 章 柔性流水车间调度问题 3,1,2,4,5,6,7,8,9 ，此时的目标函数值为 221520。第二步，调整作业 5，得到的新的作业排序为 3,5,1,2,4,6,7,8,9 ，此时的目标函数值为 220040。第三步，调整作业 8，得到新的作业排序为 3,5,8,1,2,4,6,7,9 ，此时的目标函数值为 219240。第四步，调整作业 6，得到新的作业排序为 3,5,8,1,6,2,4,7,9 ，此时的目标函数值为 219110。此时通过互换操作得到 PFS 问题的一个最优排序。图 3-2 表示该例子的最终排序方案。图 3-1 初始作业序列

【参考文献】：
期刊论文
[1]基于混合化学反应算法的柔性作业车间调度[J]. 肖华军,柴子力,张超勇,孟磊磊,任亚平,梅慧文.  计算机集成制造系统. 2018(09)
[2]基于规则导向的柔性作业车间多目标动态调度算法[J]. 朱伟.  系统工程理论与实践. 2017(10)
[3]分层混合遗传算法求解柔性作业车间调度问题[J]. 田旻,刘人境.  工业工程与管理. 2017(05)
[4]面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 李聪波,沈欢,李玲玲,易茜.  机械工程学报. 2017(05)
[5]基于混沌量子算法和MAGTD的多目标FJSP求解策略[J]. 宁涛,王旭坪,焦璇.  运筹与管理. 2017(01)
[6]基于改进教学算法的车间作业调度问题[J]. 张梅,吴凯华,胡跃明.  控制与决策. 2017(02)
[7]混合离散蝙蝠算法求解多目标柔性作业车间调度[J]. 徐华,张庭.  机械工程学报. 2016(18)
[8]基于新型邻域结构的混合算法求解作业车间调度[J]. 赵诗奎.  机械工程学报. 2016(09)
[9]DBR理论求解柔性作业车间调度问题[J]. 张国辉.  运筹与管理. 2016(01)
[10]基于多规则资源分配的柔性作业车间调度问题多目标集成优化方法[J]. 高丽,周炳海,杨学良,王吉霞.  上海交通大学学报. 2015(08)

博士论文
[1]柔性开放车间调度算法研究[D]. 展勇.哈尔滨工程大学 2011

硕士论文
[1]基于分枝界限法的开放车间调度问题的研究[D]. 刘成浩.沈阳工业大学 2012
[2]一种开放式车间调度算法及其在MES中的应用[D]. 陶伟.华中科技大学 2012
[3]基于线性松弛的并发开放式车间调度问题研究[D]. 周金阳.哈尔滨工程大学 2012



本文编号：2965076