基于元启发式的分布式车间调度方法研究

发布时间：2020-11-21 20:44

　　 随着现今市场和制造全球化趋势,为应对瞬息万变的市场需求,生产车间已经由单一车间向多车间转变,从集中式结构变为分散式结构,形成了分布式车间生产模式。车间调度在分布式车间生产中至关重要,有效的调度算法和优化技术能够优化生产系统流程,提高生产效率和经济效益。分布式车间调度问题相对单车间调度问题更加复杂,尤其是调度方法的研究,已经引起了学术界和工业界的广泛关注。许多分布式车间调度问题是NP(non-deterministic polynomial)难问题,传统的调度方法如分支定界法、数学规划方法、启发式规则,都很难获取问题的最优解或者计算量太大。元启发式算法(meta-heuristics)不依赖求解问题,通过全局和局部搜索能够获得较为满意的解,是求解调度问题的有效方法,其研究成果具有重要的学术意义和应用价值。本文深入研究了制造系统中广泛存在的零等待、零空闲、交货期等加工约束,提出了基于改进的教学优化算法以及Memetic算法的调度方法。并将相关成果扩展到分布式调度车间调度中,对分布式零等待流水车间调度以及带有装配过程的分布式零空闲流水车间调度问题进行了求解。主要研究工作如下:(1)针对教学优化算法存在的不足,从概率理论的角度出发,提出了基于概率分布模型的协同学习机制,将概率模型嵌入教授或者学习阶段,即将概率分布作为老师或者信息交流平台。针对零等待流水车间调度问题,提出了一种基于概率学习阶段的离散教学优化算法(HDTPL)。该算法通过对工件序列邻域变换来模拟教授过程,同时采用概率模型作为知识收集的平台,每个学生通过该平台交流学习,实现了学生之间的自学习。基于标准测试用例的测试结果验证了HDTPL有效性和优越性。(2)研究了分布式零等待流水车间调度问题,建立了该问题的混合整数规划模型以及提出了若干邻域变换的加速算法,有效的减少了计算的复杂度。针对分布式零等待流水车间调度问题,结合变邻域搜索、变邻域下降搜索、随机变邻域提出了三种迭代贪婪算法IG_VNS、IG_VND、IG_RNS。大量仿真实验,表明所提出的算法求解效果优于当前同领域其他分布式车间调度算法。(3)研究了带有准备时间多目标分布式零等待流水车间调度问题,考虑了最大完成时间和总延迟时间为优化目标。在每台机器上,从当前工件加工完成到下一工件开始加工前存在准备时间。提出了一种基于Pareto非支配解的分布估计算法求解上述问题。建立了三种概率模型,即工件在空工厂的概率、两个工件在同一工厂的概率、两个工件相邻的概率。在该模型的基础上,提出了一种基于参考模板的采样算法来产生后代,并对档案集以及后代个体进行了多目标局部搜索。实验表明,所提出的算法优于其他相关算法,并且所得到的解具有良好的分布性和逼近性。(4)针对零空闲流水车间调度问题,提出一种基于直方图模型的Memetic算法(MANEH)。MANEH考虑了工件的顺序以及相似工件块,采用基于混合边和点直方图模型的随机采样交叉方式,避免工件选择的盲目性。在局部搜索部分,在变邻域搜索中加入了随机参考邻域搜索以及基于模拟退火的接受准则,使得局部搜索能力进一步提高。基于大规模测试用例的实验验证了MANEH优越性。(5)针对带有交货期约束的零空闲流水车间调度问题,提出一种基于概率教授的离散教学优化算法(HDTLM)。在教授阶段,根据优秀学生个体和教师构建概率模型,对概率模型采样生成一系列位置序列;采用共有序列的概念来代替原始教学优化算法平均个体的概念,根据位置序列和共有序列来产生新个体。在学习阶段,根据学生的学习水平,将学生分为三个层次,从上到下传递知识。通过与当前较为先进的几种算法对比,验证了HDTLM的优越性。(6)研究了带有装配过程的分布式零空闲流水车间调度问题。针对已有工件分配规则的不足,提出了一种工件分配规则,使得同一产品的相关工件加工顺序尽可能紧凑,同时使得装配过程尽早开始,减少装配等待时间。针对带有装配过程的分布式零空闲车间调度问题,提出混合迭代局部搜索(HILS)算法和混合变邻域搜索(HVNS)算法。通过求解标准测试用例,验证了HILS和HVNS的性能显著优于同领域同其他相关算法。
【学位单位】：南京航空航天大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP18;TH186
【部分图文】：

3 1 3 3 3 3 3 3 3 0.344 0.182 0.188 1.472 0.801 0.514 0.584 1 4 4 4 4 4 4 4 0.435 0.195 0.169 1.616 0.855 0.541 0.635 2 1 2 3 4 1 1 4 0.302 0.192 0.157 1.138 0.563 0.402 0.456 2 2 1 4 3 4 3 3 0.343 0.202 0.210 1.515 0.805 0.574 0.607 2 3 4 1 2 3 2 1 0.346 0.229 0.259 1.198 0.753 0.738 0.588 2 4 3 2 1 2 4 2 0.479 0.247 0.283 1.680 0.919 0.777 0.739 3 1 3 2 2 4 2 2 0.349 0.177 0.195 1.483 0.819 0.641 0.6110 3 2 4 3 1 2 3 1 0.463 0.283 0.337 1.339 0.907 0.860 0.6911 3 3 1 4 3 1 4 4 0.455 0.178 0.221 1.644 0.931 0.605 0.6712 3 4 2 1 4 3 1 3 0.319 0.194 0.164 1.247 0.699 0.479 0.5113 4 1 4 2 1 3 1 3 0.406 0.195 0.188 1.751 0.941 0.624 0.6814 4 2 3 4 3 2 2 2 0.316 0.190 0.233 1.280 0.597 0.608 0.5315 4 3 1 1 4 1 4 1 0.437 0.333 0.300 1.124 0.816 0.803 0.6316 4 4 2 3 2 4 3 4 0.528 0.226 0.199 1.886 1.151 0.754 0.79表 2.3 各参数响应值及排名水平参数α γ ω TFCr ξ Rt Np1 0.586 0.684 0.636 0.587 0.698 0.588 0.561 0.6272 0.596 0.537 0.577 0.684 0.632 0.626 0.569 0.6053 0.625 0.620 0.731 0.633 0.600 0.593 0.670 0.5984 0.633 0.669 0.651 0.613 0.562 0.661 0.669 0.639极差 0.023 0.066 0.063 0.041 0.058 0.034 0.060 0.019等级 7 1 2 5 4 6 3 8

同工厂数量下 NEH2 以及 DNEH+Dipak 计算结果 95%置信区间olm’s procedure 检验：不同初始方法下的 IG_VNS、IG_VND、H0p α/(k-i*+1) Holm’s pDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 RDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 RDNEH=NEH2 0.0000 0.2503 RDNEH=Random 0.0000 0.0500 R0.80.70.60.5ARPDIG_RNS IG_VND IG_VNS

MDNWFSP-SDST比较算法的Pareto前沿（SSD50110测试用例）
【参考文献】

相关期刊论文 前2条

1 王圣尧;王凌;方晨;许烨;;分布估计算法研究进展[J];控制与决策;2012年07期

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

相关博士学位论文 前2条

1 胡忠义;基于文化基因算法的电力负荷预测模型及应用研究[D];华中科技大学;2015年

2 张超勇;基于自然启发式算法的作业车间调度问题理论与应用研究[D];华中科技大学;2007年

相关硕士学位论文 前1条

1 张富生;基于遗传算法的车间动态调度研究[D];山东大学;2013年

本文编号：2893574