混合粒子群算法在动态车间调度中的应用
来源:用户上传
作者:楚学伟
摘 要：车间调度问题是广泛存在于现实生活中的经典算法规划问题。好的生产调度系统有利于提高企业工作效率及降低企业成本，是工业生产的核心竞争力。粒子群算法因为强大的智能规划能力而被广泛用于车间调度问题当中。文章在原有标准粒子群算法基础上，引入模拟退火机制及遗传算法中交叉变异策略形成的混合粒子群优化算法，并在更具有实际生产环境的动态车间调度中模拟应用，与遗传算法、离散粒子群算法进行比较，具有较强优势。
关键词：模拟退火;交叉变异;混合优化;动态车间调度
混合粒子群算法（Particle Swarm Optimization，PSO）[1]是基于没有免费的午餐定理（No Free Lunch，NFL）理论提出来的，结合粒子群算法、遗传算法交叉变异[2-3]及局部搜索算法中模拟退火机制而形成的混合智能算法，克服了传统粒子群算法容易陷入局部极值、种群单一等缺点，应用于更加贴合实际生产的动态车间调度问题（Job-shop Scheduling Problem，JSP），检测算法鲁棒性，提高了实际应用能力。
1 标准粒子群算法
PSO算法是一种群智能算法，是模拟鸟群觅食行为的仿生算法，算法中所有粒子都用目标函数来评价该粒子当前位置的优劣，通过算法迭代，每个粒子受到自身及其他粒子的影响，更新自身速度与位置，通过目标函数确定当前个体最优位置pbest及全局最优位置gbest。每次迭代粒子的更新公式如下：
Vit+1=ωVit+c1γ1（Pit-Xit）+c2γ2（Pgt-Xit）（1）
Xit+1=Xit+Vit+1（2）
公式（1—2）可看作由N个粒子组成的一个群体，在D维搜索空间中，ω为非负常数，表示惯性权重;c1，c2为学习因子。γ1，γ2为[0，1]的随机数，为调节系数，向量Xit表示第i个粒子在第t次迭代后粒子所在的位置，Vit表示第i个粒子在第t次迭代后粒子所拥有的速度，第i个粒子t次迭代后个体最优解为Pit，全局最优解为Pgt，式中c1γ1（Pit-Xit）表示粒子更新迭代時对自身位置、速度的继承行为，c2γ2（Pgt-Xit）表示粒子更新迭代时，搜索空间中其他粒子速度对其影响行为。
2 混合粒子群算法
粒子群算法虽然具有很多优点，但其在运算过程中有容易陷入局部极值、鲁棒性不强等致命缺点。针对以上情况，本研究提出对粒子群算法的几点改进：增加局部搜索策略，引入模拟退火极值，提高局部搜索算法精度;在种群多样性方面，引入遗传算法中的交叉变异策略，动态调节种群多样性，增强算法鲁棒性。
2.1 局部搜索策略
模拟退火思想[4]来源于物理退火原理，分为加温、平衡、冷却3个阶段。加温是使固态物体变为液态的过程，由相对稳定状态转为不平衡状态，同时，固态液化，消除固态时的不均匀状态;平衡阶段是物体与周围环境进行热量交换的过程，当物体的自由能降到最低时，系统达到平衡状态;冷却阶段是物体由液态凝固到固态的过程，在此阶段，系统内能量逐渐减少，物体内粒子相对运动减弱，物体由液态变为固态。模拟退火算法可以接受比当前更差的解，因此，具有很好的局部搜索能力。
模拟退火机制利用Metropolis接受机制[5]，有一定概率会产生较差邻域解，从而使得新解跳出局部极值，实现全局搜索的目的。设目标函数为f（x），当前迭代次数时全局最优解为f（x1），产生邻域解为f（x2），两者差值设定df=f（x2）- f（x1），则Metropolis准则接受邻域值得概率p为：
（3）
由公式（3）可以看出，当df<0时，一定会产生新的邻域解，即当前迭代没有达到局部最优解状态，可继续产生最优解;当df≥0时，算法以概率接受邻域解，即当前全局最优解好于邻域解时，会以一定概率产生邻域较差解，以便跳出局部极值，达到全局搜索目的。
2.2 交叉变异策略
交叉变异操作[6]是遗传算法的重要组成部分，算法通过交叉操作从父代获取有利基因，淘汰不利基因，从而让后台保持有利基因;算法通过变异操作引导算法向适应度更高的最优解靠拢，更好地实现全局搜索，增强种群多样性。
2.2.1 交叉操作
两个父代粒子x1，x2，将x1粒子随机选中和保留粒子的基因位，并记录选中基因个数，在x2粒子随机选中与x1粒子选中基因相同的对应基因位，并保留其所在基因，复制到子代y粒子中，同时，将x1粒子中保留基因按照顺序重新排列插入到子代粒子中，完成交叉操作，如图1所示。
2.2.2 变异操作
变异操作是提高种群多样性的有效途径，引导算法向更高的适应度函数进化。变异操作是随机选择父代基因中基因片段的多组不同基因位进行互换，如果调换位置的基因位相同，则父代基因与变异后的子代基因相同，实质上没有进行变异，图2为两组基因位变异操作。
3 动态车间调度
动态车间调度是针对传统静态车间调度问题提出来的[7]，加工环境更加复杂，受外界不可抗力的干扰更多，更加符合现代工业生产的需要。
3.1 问题描述
静态车间调度问题来源于传统工业生产，是从实际问题中产生的抽象数据模型。假设N个工件在M台机器上进行加工，则在静态车间调度下，工件和机器需要满足的约束条件包括：（1）预先指定工件加工工序。（2）预先指定加工时间与加工机器，不得随意更改。（3）同一时间，一台机器只能加工一个工件。（4）无特殊指定，工件加工优先级一样[8]。在此基础上，动态车间调度增添外界干扰因素，例如：增加紧急订单、取消订单、机器故障等突发事件。 3.2 动态调度窗口
静态车间调度系统一旦初始开启调度，后期加工就按照原有初始调度执行，不能出现偏差。而在动态调度系统中，由于不可抗力等突发情况打破了原有调度系统，破坏了初始调度规则，把产生突发事件时需要暂停调度的窗口称为动态调度窗口[9]。由此，动态车间调度可以看成多个静态车间调度系统的集合，发生突发事件的动态调度窗口立即暂停当前静态调度系统，等待资源分配后进行下一次调度。图3为动态调度窗口，在ti时刻，由于发生突发事件，机器不再执行原有调度程序算法，暂停执行。
3.3 数据模型修复
当调度系统由于发生突发事件而产生动态调度时，原有调度系统暂停，在开启新的静态调度系统之前，要保证所有加工机器及工件等资源已准备就绪，需要进行数学模型修正。
3.3.1 加工时间修正
当在ti时刻发生动态调度时，加工工件所处状态为3种：（1）已加工、正加工及待加工状态，由于调度系统暂停，待加工工件将不再进行加工工作。（2）正在加工工件不打断问题连续性，将继续加工至完成。（3）已加工工件正常退出加工调度系统流程。
3.3.2 修复时间修正
当在ti时刻发生动态调度时，加工机器所处状态为3种：（1）空闲、正加工、故障，由于调度系统暂停，本处空闲状态机器不再加工工件。（2）正加工工件不打断问题连续性，将正加工工件加工完成。（3）故障机器在指定修复时间内完成修复，重启调度系统。
4 仿真模拟实验
本研究在经典实例FT06基础上引入突发机器故障情况，以最短加工时间为优化目标，讨论混合粒子群算法与遗传算法、离散粒子群算法[10]对此类问题的求解。依照FT06经典实例有以下时间加工矩阵及机器加工矩阵：
Jt=，Jm=
假设t=26时，机器4故障，修复时间为9。如图4所示，当t=26时，机器4故障，机器2此时处于空闲状态，由于调度暂停，不再接受调度任务，机器1，3，5，6保持问题连续性，不打断正在加工工件，可保持正常运行至加工完成，t=35时刻，机器4修复完成，资源重新分配，重启调度系统。
本研究对FT06测试实例分别在加急订单、取消订单、机器故障情况下，与遗传算法、离散粒子群算法进行对比实验，如表1所示，在加急订单情况下，离散粒子群算法无法完成寻优情况，程序中断;在取消订单、机器故障等情况下，混合粒子群算法优于离散粒子群算法与遗传算法。为进一步验证混合粒子群算法收敛性、鲁棒性，将FT06动态实例问题用3种算法分别求解10次，每种算法迭代200次，如图5所示，可以看出，混合粒子群算法在动态车间调度上收敛速度和收敛效果都优于离散粒子群算法（Discrete Particle Swarm Optimization，DPSO）、遗传算法（Genetic Algorithm，GA）。
5 結语
在标准粒子群算法基础上引入模拟退火机制，增强局部搜索能力，增加遗传算法中交叉变异策略，增添除原有影响外的其他参考点，增强种群多样性，并将算法应用于动态车间调度，考虑加急订单、取消订单、机器故障等突发情况，与DPSO，GA算法进行对比实验，实验结果表明混合粒子群算法在动态车间调度中收敛性更强，收敛速度更快，鲁棒性更好。
[参考文献]
[1]EBERHART R，KENNEDY J.A new optimizer using particle swarm theory[C].Nagoya：the 6th International Symposium on Micro Machine and Human Science，1995.
[2]鞠全勇，朱剑英.基于混合遗传算法的动态车间调度系统的研究[J].中国机械工程，2007（1）：40-43.
[3]于莹莹.改进自适应遗传算法在作业车间调度问题中的应用研究[D].大连：大连交通大学，2012.
[4]王莹，曹军，张福元.基于模拟退火的改进混沌粒子群算法[J].内蒙古工业大学学报（自然科学版），2017（3）：173-177.
[5]林敏，刘必雄，林晓宇.带Metropolis准则的混合离散布谷鸟算法求解旅行商问题[J].南京大学学报（自然科学），2017（5）：972-983.
[6]寇保华，杨涛，张晓今，等.基于交叉变异的混合粒子群优化算法[J].计算机工程与应用，2007（17）：85-88.
[7]刘建国，朱恒民，王宁生.混合流水车间符合平衡调度的免疫算法[J].西安电子科技大学学报（自然科学版），2006（4）：655-659.
[8]刘辙，杨敬松，崔广才.Job-shop Scheduling问题的研究[J].长春理工大学学报，2003（3）：12，19-21.
[9]张超勇，李新宇，王晓娟，等.基于滚动窗口的多目标动态调度优化研究[J].中国机械工程，2009（18）：2190-2197.
[10]王磊.基于改进离散粒子群算法的作业车间调度方法研究及应用[D].杭州：浙江工业大学，2012.
Application of hybrid particle swarm optimization in dynamic workshop scheduling
Chu Xuewei
（College of Information and Technology， Jilin Normal University， Siping 136000， China）
Abstract：Workshop scheduling problem is a classic algorithm planning problem widely existing in real life. A good production scheduling system is conducive to improving the work efficiency and reducing the cost of the enterprise， and is the core competitiveness of industrial production. Particle swarm optimization is widely used in workshop scheduling problems because of its powerful intelligent planning capabilities. Based on the original standard particle swarm algorithm， the hybrid particle swarm optimization algorithm formed by simulated annealing mechanism and cross variation strategy in genetic algorithm is introduced in this paper， and it is used in dynamic workshop scheduling with more practical production environment， compared with genetic algorithm and discrete particle swarm optimization， it has strong advantages.
Key words：simulated annealing; cross mutation; hybrid optimization; dynamic shop scheduling
转载注明来源:https://www.xzbu.com/8/view-15197328.htm
