论文研究-改进离散差分进化算法在分布式车间调度问题中的应用 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.30M 资料格式：pdf 举报版权申诉

weixin_39840914-11571030-4744302543303686179.pdf-第1页.png

第1页 / 共6页

weixin_39840914-11571030-4744302543303686179.pdf-第2页.png

第2页 / 共6页

weixin_39840914-11571030-4744302543303686179.pdf-第3页.png

第3页 / 共6页

weixin_39840914-11571030-4744302543303686179.pdf-第4页.png

第4页 / 共6页

weixin_39840914-11571030-4744302543303686179.pdf-第5页.png

第5页 / 共6页

weixin_39840914-11571030-4744302543303686179.pdf-第6页.png

第6页 / 共6页

文本预览

中国科技论文在线 http://www.paper.edu.cn 改进离散差分进化算法在分布式车间调度问题中的应用王艳红，盛舒婉* 5 10 （沈阳工业大学信息科学与工程学院，沈阳 110870）摘要：随着网络技术的发展分散网络化制造逐渐引起人们的关注。分布式车间调度是分散网络化制造的一种实现手段。为了解决分布式车间调度，针对差分进化算法的连续特性，提出一种改进离散差分进化算法。该算法采用基于工件的编码方式，面对解决离散问题时交叉操作产生不可行解的情况，从原理上对交叉操作进行修复，确保离散后的算法最大程度贴近原算法，使原算法准确性和高效性得到延续。用提出的算法求解分布式车间调度问题实例，结果表明此算法是一种求解分布式车间调度问题的有效算法。关键词：分布式车间调度；差分进化算法；离散化中图分类号：O231.9 15 Modified discrete differential evolution algorithm for distributed Job Shop Scheduling Problem (Shenyang University of Technology, School of Information Science and Engineering, Shenyang WANG Yanhong, SHENG Shuwan 110870) Abstract: With the development of network technology, it has gradually attracted people's attention. Distributed job shop scheduling is one of the means to realize the distributed network manufacturing. In order to solve the distributed job shop scheduling ,aiming the continuous characteristics of differential evolution algorithm an improved discrete differential evolution algorithm is proposed. The algorithm code by artifact and improved the crossover operator to directly generate feasible solutions. It can ensure the discrete algorithms can be most close to the original algorithm, and the accuracy and high efficiency can be carry on. Use the algorithms to test the Distributed Job Shop Scheduling Problems, the results indicate the effectiveness of the proposed algorithms. Key words: distributed discretization job shop scheduling problem; differential evolution algorithm; 20 25 30 0 引言对作业车间调度问题的优化是一种典型的组合优化问题[1]。组合优化问题的显著特点 35 为，随着问题规模的增大，搜索空间急剧增加[2]。针对组合优化问题的这种特点，传统的优化算法很难甚至不能求出问题的最优解。差分进化算法是一种群体智能优化算法,具有收敛速度快、原理简单、控制参数少和进行随机、并行的全局搜索等优点，广泛应用于实际问题中[3]。长期以来，对差分进化算法的研究主要集中在连续变量问题上，并且显示出突出的效果。基于差分进化算法的优越性，大家越来越多把目光转移到解决离散变量问题中。对分布 40 式作业车间调度问题的优化具有离散特性，对于此种带有约束的优化问题，对不可行解的处理方法直接关系到算法的性能[4]。基本离散差分进化算法应用于调度问题时，对于交叉操作后生成的不可行解直接采用随机方法进行修复，大大降低了原算法的寻优能力。本文提出的改进离散差分进化算法对不可行解依据交叉原理重新选择排列生成可行解，最大程度遵循原作者简介：王艳红(1967-),女,教授,智能制造、生产计划与调度等. E-mail: shengsw1130@163.com - 1 -

中国科技论文在线 http://www.paper.edu.cn 算法的原理，确保离散后算法的准确性和寻优能力。 45 1 基本离散差分进化算法差分进化算法是一种采用浮点矢量编码,进行启发式随机并行搜索的群体智能算法[5]。它依据父代个体之间的差异进行变异、交叉和选择操作。 1.1 变异操作变异操作是整个差分进化算法的核心，是算法对差分两个字的体现[6]。对于种群规模为 50 ，解空间维数为的第代个体来说，变异操作即为把种群中随机选择的两个个体相减，乘以变异因子加到随机选择的第三个个体上来进而对每个个体进行变异生成变异个体，表示如下 (1) (2) 55 其中随机选择的三个个体号互不相等，并且与当前个体也不相等。和分别为当前迭代次数和最大迭代次数。其中变异因子采用自适应因子, 如公式(2)所示[7]，其中，。此步骤中的乘运算可能会产生不符合调度规则的小数。对于这种情况，采用离散原则，即对公式(1)进行四舍五入。 1.2 交叉操作 60 交叉操作用来增加种群多样性。种群中的当前个体与变异个体在每一位上依据交叉概率因子进行交叉操作，生成试验个体。具体操作如公式(3)所示 (3) (4) 其中 rand 为区间内均匀分布的随机数，为交叉概率。此文中选用自适应交叉 65 概率，如公式(4)所示。越大，试验个体从变异个体中的得到的元素更多。 rand 为中随机选取的整数，用来确保试验个体中的元素至少有一位由变异个体提供，以保证个体的进化。 1.3 离散操作差分进化算法在进行变异和交叉操作后，由于调度问题的结构特点，都可能产生不可行 70 解。变异操作的功能为增加种群的多样性，可以接受不可行解。试验个体要参与到选择操作中，必须要求其为可行解。基本差分进化算法必须在此处加入离散方法，即对生成的试验个体进行检测，如果其为不可行解，则对该个体重新随机生成一个可行解。 1.4 选择操作差分进化算法采用贪婪的选择方式，把试验个体与当前个体进行竞争[8-9]。当试验个体 - 2 - NPDGGiX123*()GGGGirrrVXFXX2maxmaxminmax()*()GFFFFG1,2,3{1,2,...,NP}rrriGmaxGmax0.9Fmin0.2FGiXGiVGiU,j(1,D),GiGiGiVrandCRrandUX或其他2maxminmax=(-)*()GCRCRCRG[0,1]CRCR{1,2,...,D}GiU

中国科技论文在线 http://www.paper.edu.cn 75 的适应度小于当前个体的适应度时才被保留到下一代，否则当前个体直接进入下一代进行计算。具体操作如公式(5)所示其中代表适应度函数，代表新生成的种群个体。 (5) 2 改进离散差分进化算法 80 2.1 算法概述分布式作业车间调度问题可归结为非线性整数规划问题，对其的优化即为带有约束的优化问题。对于此种问题的优化，针对不可行解的处理方法，直接影响到离散后算法的搜索性能和优化能力[10]。所以在把差分进化算法应用于调度问题上时，离散操作直接决定离散差分进化算法是否可以保留原差分进化算法的寻优能力。基本离散差分进化算法的离散操作直 85 接对不可行解进行重新随机生成一个可行解。此操作破坏了原差分进化算法的基本原理，对算法的准确性有所扰动。本文在此步骤提出一种混合的离散操作。检测到试验个体有不可行解的情况后，对其重新进行交叉操作。即如果原来某位依据交叉概率由变异个体提供，则更改交叉概率，使该位改变由当前个体提供。这种离散操作，依据原算法原理对不可行解进行处理，在最大程度上贴近原差分进化算法的准确性。确保离散后的差分进化算法应用在车间 90 调度问题上可以准确找到最优解。 2.2 算法实现步骤 1 依据基于工序编码原理，检测试验个体是否为可行解。若是，则结束程序进行选择操作。步骤 2 找出试验个体出现次数最多和最少的工件号。 95 步骤 3 按顺序查看位对应的父代。如果该位原来由变异个体提供，则查看另一父代该位的值是否为。若是，则进行离散操作，把试验个体该位换成由另一父代提供的，反之亦然。返回步骤 1；否则按顺序继续查看。步骤 4 如果所有位都不满足离散操作则进行强制转换。找出第一次出现的位置，把该位强制转换成的值，返回步骤 1。 100 2.3 应用举例在解决单车间调度问题时，本文以工序为基础进行编码。在此处举一个 3*3*3 的例子。假设种群个数为 4 ，生成的 4 个个体分别为、、、。只针对个体 1 进行分析。变异操作后，四舍五入生成的变异个体为 105 。对个体 1 进行交叉操作，假设必须由变异个体提供的位为第 4 位。父代如下、。 - 3 - GiUGiXGiX1,()(),GGGiiiGiGiUfUfXXX其他(x)f1GiXGiUGijUmaxJminJmaxJGijUGijVminJmaxJminJmaxJmaxJminJ1[1,1,2,1,3,3,3,2,3]GX2[1,2,3,3,2,1,1,2,3]GX3[2,2,3,3,1,2,1,1,3]GX4[3,3,3,2,2,1,1,2,1]GX1[3,2,3,2,2,1,3,3,2]GV1[1,1,2,1,3,3,3,2,3]GX1[3,2,3,2,2,1,3,3,2]GV

中国科技论文在线 http://www.paper.edu.cn 这时依据交叉概率，假设生成的试验个体。很明显此次交叉操作生成的试验个体为不可行解。根据交叉概率重新选择，使试验个体 110 的第 2 位由当前个体提供，而不是变异个体提供。则试验个体可变成。试验个体仍为不可行解，但是最多出现工件号 2 的其余位都不能依据交叉原理重新改变成最少工件号 1。这时进行强制转换，把试验个体的第 3 位强制转换成，则试验个体变为。依据工件编码原理，此解为可行解。以上可以看出处理完的试验个体还是依据原父代进行组合排序的。相比于基本离散算 115 法中，对不可行解直接随机重新生成一个可行解，此改进最大限度贴近原始差分进化算法，使离散后的差分进化算法具有原算法的准确性和优越的搜索能力。 3 仿真研究 3.1 问题描述本文以实际的分布式车间调度问题为例进行实验。假设一总工厂有3个分工厂，每个工 120 厂有4台机器。目前这3个分工厂都可以处理一批工件，这批工作包含5个工件，每个工件包含4道工序。具体约束条件如下表所示表1 分布式车间调度加工约束 Tab.1 Distributed scheduling process constraint 工件号 Job1 Job2 Job3 Job4 Job5 Operations1 F1-M1(2) F2-M2(8) F3-M4(15) F1-M2(15) F2-M1(2) F3-M3(6) F1-M4(9) F2-M1(2) F3-M2(19) F1-M1(7) F2-M1(20) F3-M3(2) F1-M4(2) F2-M1(9) Operations2 Operations3 Operations4 F1-M3(1) F2-M1(4) F3-M3(10) F1-M3(20) F2-M2(2) F3-M1(8) F1-M2(10) F2-M3(1) F3-M3(20) F1-M4(7) F2-M3(20) F3-M1(2) F1-M2(1) F2-M3(6) F1-M2(3) F2-M3(6) F3-M1(20) F1-M1(20) F2-M3(4) F3-M2(5) F1-M1(2) F2-M2(1) F3-M1(20) F1-M3(6) F2-M2(25) F3-M2(4) F1-M1(1) F2-M4(7) F1-M4(4) F2-M4(3) F3-M2(20) F1-M4(20) F2-M4(1) F3-M4(4) F1-M3(6) F2-M4(5) F3-M4(20) F1-M2(4) F2-M4(19) F3-M4(3) F1-M3(4) F2-M2(5) F3-M2(20) F3-M4(10) F3-M1(10) F3-M3(20) 为了更好地验证结果，一些工件的加工时间明显区别于它的其它平行的生产计划。例如 125 工件1在工厂1的加工时间明显优于其在工厂2和工厂3中的加工时间。同理工件3在工厂1和工厂3的加工时间明显多于在工厂2的加工时间。这样分析，工件1应首先选择在工厂1工作，而工件3应首先在工厂2工作可能使最大完工时间会最短。 3.2 仿真结果设置种群规模，最大迭代次数，变异因子和交叉概率因子 130 如公式(2)和(4)所示。以最大完工时间最短作为目标函数。各个工厂加工的甘特图如下图所示： - 4 - 1[1,2,2,2,2,3,3,3,2]GU12GU12GX1GU[1,1,2,2,2,3,3,3,2]132GU131GU1[1,1,1,2,2,3,3,3,2]GU400NPmax200GFCR

中国科技论文在线 http://www.paper.edu.cn 图 1 工厂 1 的加工甘特图 Fig.1 The Gantt chart of factory 1 图 2 工厂 1 的加工甘特图 Fig.2 The Gantt chart of factory 2 图 3 工厂 1 的加工甘特图 Fig.3 The Gantt chart of factory 3 135 140 由以上结果分析可知，此实例的最大加工时间为 12 个单位时间。其中由于耦合关系，工件 1、3、5 在某些工序上并不是在最优工厂中加工。其中工件 1 的第 4 道工序如果单纯分析其在各个工厂的加工时间，其明显在工厂 1 的总加工时间最少。但是由于要考虑全部工件的加工时间，所以工件 1 的第 4 道工序则选择在工厂 2 的机器 4 上加工。但是比较可知，相 145 比于在工厂 1 加工工件 1，工序 4 省了一个单位时间。 4 结论对分布式作业车间调度问题的优化可以看成是带约束的优化问题，此种问题对不可行解的处理方法直接影响到离散后算法的可行性和优越性。为了确保离散后差分进化算法能更准确的应用到调度问题上，在基本离散差分进化算法的基础上，提出改进离散差分进化算法。 150 改进后的离散差分进化算法更大程度遵循原差分进化算法原理，保持了差分进化算法的优越性。根据仿真结果表明，改进后的离散差分进化算法具有可行性，相对于基本离散差分进化算法来说，具有更强的搜索能力，很好的保持了原差分进化算法的收敛性。 - 5 -

中国科技论文在线 http://www.paper.edu.cn [参考文献] (References) 155 160 165 170 [1] Keesari H S, Rao R V. Optimization of job shop scheduling problems using teaching-learning-based optimization algorithm[J]. OPSERCH, 2014, 51(4): 545-561. [2] 季晓慧,张健.约束问题求解[J].自动化学报,2007,33(2):126-130. [3] Storn R, Price K. Differential evolution -A simple and efficient adaptive scheme for global optimization over continuous spaces[R]. Berkeley: University of California, 2006. [4] B.Naderi, A.Azab. Modeling and heuristics for scheduling of distrubuted job shops[J].Expert Systems with Applications,2014,41(2014):7754-7763. [5] 张春美.差分进化算法理论与应用[M].1 版.北京：北京理工大学出版社,2014: 5-19. [6] 刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,2007,22(7):722-729. [7] 肖术骏 , 朱学峰 . 一种改进的快速高效的差分进化算法 [J]. 合肥工业大学学报 ( 自然科学版),2009,32(11):1701-1703. [8] 桑红燕 , 潘全科 , 潘玉霞 , 等 . 求解批量流水线调度问题的离散差分进化算法 [J], 计算机仿真,2010,27(7):292-295. [9] Wen L, Xi M L, Ya F H, et al. A hybrid differential evolution augmented Lagrangian method for constrained numercal and engineering optimization[J]. Computer-Aided Design, 2013, 45(12): 1562-1574. [10] Huang F Z, Wang L, He Q. An effective coevolutionary differential evolution for constrained optimization[J]. Applied Mathematics and Computation, 2007, 186(1): 340-356. - 6 -

分享到：

赞收藏

资料库

论文研究-改进离散差分进化算法在分布式车间调度问题中的应用 .pdf

相关推荐

开发技术

热门标签

最新资料