针对工艺规划与调度集成（integration of process planning and scheduling，IPPS）问题求解复杂性，为提高求解效率，设计了包含探索种群、寻优种群和最优种群的多群体混合进化算法，通过运用混合遗传算法和基于聚类淘汰机制的差分进化算法分别更新探索种群中工艺链和加工顺序链，保持可行解多样性和差异性；然后利用克隆领域搜索算法完成寻优种群中可行解的克隆和领域搜索，进一步提高种群质量；最后按照精英保留策略更新最优种群获得全局最优解。通过实例计算对比，结果显示算法搜索效率和求解质量均有明显改善，且稳定性较好，表明该算法求解IPPS问题的可行性及优越性。
2596· 计算机应用研究 2017年 2(z<TN2)条加工顺序链之一;(b)记录l1与中心点数值相同更新。 的位置;(c)l2同位置的值赋予l3;(d)基于l工序顺序补足l3 h)如果t=T,则输出最优种群中最优解,否则继续探索种 其他位置数值。交叉操作如图3所示。 群的更新」 机选取把每条链 2.4算法步骤 )到,重新确定各<手心点变位型输出 海明距离类别中心点 综合以上提出的混合遗传算法和基于聚类淘汰机制的差 类别中心最小类中 各类别 分进化算法更新工艺链和加工顺序链;寻优种群进行领域搜索 图2聚类流程 后更新最优种群。求解IPPS问题的多群休混合进化算法流程 如图5所示。 相同值位置 2|56381101479 始) 输入所有工仁信息 图3交又操作图 探索科群初始化 d)对个体进行扩散搜索,基于差分进化算法夏新加顺④出快是<思条少 序链,按照式(8)牛成n,并对n;中数据升序排列之后所在位 遄传盆定探索种群中工探家种群中加工差分选择克降个 置替代原来的值,如v;第三列数值升序排列后处于第六位,则 顺序链进行进 克隆个体组洲领域 ;(3)=6,其中x2和x3为种群中不同于x;的加工顺序链。 及被<机数 群杭 (8 更新工艺链交 更新 v=ri+Fx(K3-x 卣喇區 变异 e)各工件对加工顺序基于升序规则调整。 没备链变异 神君「 2.3寻优种群搜索及最优种群更新 设备链}[工之链 运用克隆领域搜索算法更新寻优种群,在克隆个体选择时 引人反馈淘汰机制,避免种群陷亼局部最优。寻优完成后更新 採探索种群 最优种群。步骤如下 图5MG-HEA算法流程 a)确定克隆数量b和规模q,反馈系数n,迭代次数t,最大 a)输人工件和设备信息,包括各工件工艺路线集、设备集 迭代数,最优种群规模BNV。 和设备数量等; b)反馈洵汰机制选择克隆个体。即:(a)当t<u时从探索 b)随机选择工件工艺路线、工序加工设备和加顺序完 种群中选取适应度值最高的前b个个体进行克隆;(b)当t>n成探索种群初始化; 时,当(a)选择的个体中与最优种群里个体相同且连续u次迭代 c)计算种群适应度,如果满足求解目标则输出最优解,否 不变时,基于适应度值顺延方式选择其他个体替代该个体。 则进入d)e); c)每个个体克隆q次组成寻优种群。 d)混合遗传算法更新工艺链,随机选择加工没备,组成设 d)确定选择率P2和最优特征信息(最优种群中适应度最备链 高两个个体的相同工艺信息。生成随机数n2,如果r2≤P2或最 )使用混合聚类算法淘汰加工顺序链并采用差分变异操 优种群为空,则工艺链第r3个工件工艺路线变异;当n2>P2,如 作更新,之后基于改进差分进化算法更新加顺序链 果最优特衎信息为空,与最优个体进行交叉,否则复制最优特 f)计算探索种群适应度,基于迭代次数与反馈淘汰系数选 征信息到工艺信息中,之后更新设备链,比较变异前后适应度择个体进行克隆; 保留更优个体。具体流程如图4所示。 g)采用领域搜索算法更新寻优种群,分别更新工艺链、设 输人1艺链→确定随机数四 备链和加工顺序链; 第n个工件的工艺 h)基于优胜劣汰规则更新最优种群; 路线变异 i)判断是否满足优化目标,满足则输出最优解,否则转人 最优特征信息为空? 是与最优工件进行 3实验及结果分析 最优特征信息替换 到工艺链对应位置 本文运用MG-HEA算法求解问题,为了验证算法的 输出工艺链 可行性和有效性,采用 MATLAB软件实现。由于IPPS问题没 图4工艺链操作流程 有标准测试数据库,以某汽车焊装车间数据进行仿真,具体数 )寻优种群中的设备链进行变异,随机选取设备链中r3据如表2所示。 (r3<n/2)个位置的设备进行替换,变异后根据适应度值保留 木文分别采用 MG-HEA算法、GA算法、HACO算法 更优个体的设备链。 和HPSO算法0求解该实例,相关参数设置如下:迭代次数T ∫)随机生成炳个不同的变异点乃3和4,交换加工顺序链为100,种群规模为200,工艺选择率p为0.5,聚类种群数量c 中p3和P位置所对应的数值,并按照工艺顺序约束进行调为5个,洵汰概率P,为0.4,差分进化算法变异算子F为0.6, 氅,之后基于精英选择策略保留更优的加工顾序链。 寻优种子数b为10,克隆规模q为9,反馈淘汰指数u为5。为 )更新最优种群。-1时,选择寻优种群中适应度最高了避免算法求解偶然性,每种算法仿真10次,运行完成后对结 的前BN个个体进入最优种群;否则,按照优胜劣汰规则进行果进行了相关分析。 第9期 杜轩,等:多群体混合进化算法求解IPPS问题 2597· 表2工件相关信息 M6 024|044045026 设备类型 M4031o36012 032 056 023 工件工序 工艺路线 O46 lI 014064 062 1511 1-3-5-4 6106054013 055 1-4-2-5-3 10 30 607080 图7 MG-HEA算法最优方案甘特图 2-4.5-6-3 表3不同算法实例结果 GA[3] HACo[4 IPSO[20] MG-HEA 5-2.3-6-4 最伉方案值82777572 10次平均值 8.5 76.8 1-6.5-3-2 3.2稳定性分析 6-5-3 智能算法随机性导致求解结果在一定范围内波动。由于工 件数增多,可行解数量以指数式增长,增加了最优解求解难度。 1-3-456 以运行10次平均结果相对偏差作为评价指标检验MG-HEA算 15 13 3-4-5-1 法稳定性,取不同数量工件进行测试,结果如表4所示 表4不同工件数仿真结果 工件数 平均值 最优值相对偏差 6 1-2-46-5 52 61.7 1.134 72.9 12.8 206 13 1-3-4-2-6 表4数据表明,ⅥG-HFA算法求解最优值的相对偏差随着 6 3-1-46-2 346 6-2-4-1-3 工件数増加而增大,但是相对偏差增速并没有指数式增长,而 是类似于线性增长,并且当工件数为18时,可行解的规模已经 3.1可行性和有效性分析 超过万亿,但是算法求解的相对偏差只有3.195%,表明算法 图6是运用不同算法求解IPPS问题时最优值的变化规 波动性小,稳定性较好。 律。图中显不运用HGA算法求解时收敛最早,最优解质量最3.3相关参数对算法的影响 差,因为可行解更新时过多保留了上代种群的特征,导致种群 通过研究相关参数变化对算法的影响,确定参数合理取 之间相似度较高,算法过早收敛;HACO算法优化IPS问题值保证算法求解时达到最优性能。分别改变工艺选择率p 时,最优解的优化幅度较大,但收敛速度平缓,需要花费较长时淘汰率p和反馈系数x,仿真结果如图89和表5所示。 间跳出局部最优,表明种群分布性较差;HPSO算法求解时收 敛较快,并且求解质量较好算法动态更新机制在初期较好保三一 持了种群多样性,然而由于算法搜索跨度铰大,忽略了更优可 行解,致使最优解质量尢法进一步提高。ⅥG-IFA算法求解时 0.20.40.60.8 柑对于其他三种算法搜索效率和最优解质量更高、种群分布性 b0200 较好、算法机动性较强,可以忺速跳出局部最优解,获得全局最 图8选择率变化对算法的影响图9淘汰率变化对算法的影响 优解,证明了其求解IPPS问题的可行性和有效性。 表5相关参数对算法的影响 平均值 最优值 相对偏差/% 3 72.6 0.826 HACO 72 1.639 1.63 74 73 02030405060708090100 迭代次数 图8显示随着p增大时,最优解保持不变,但平均值先减 图6不同算法最优解变化 后增,表明算法的波动性先减小后增大。因为P的取值小致使 表3显示各种算法求解IP问题时的最优值和平均值。探索种群中人多数工艺链选择变异操作,过多保留了上代种群 本文MG-IA算法求得的完工时间的最优值和平均值相较于的特征,进化速度减缓;P取值过大则导致种群较多个体选择 其他三种算法最大降幅分别为13.%、15.4%,明显优于其他交叉,丧失了自身的优良特征,致使种群盲目进化 种算法。其最优解甘特图如图7所示。 图9表明平均值随着P,增大先减后增,而且当洵汰率为 图7显示运用MGHA算法求得最优方案中同一机器大零时,无法得到最优解。囚为P过小导致种群聚集度增大,陷 多数相邻工序连续加工,而且同一工件相邻工序之间等待时间人局部最优;取值过大时,种群搜索步伐大容易忽略最优解。 较短,表明全局最优解质量较高 表5显示算法波动性随着u的增大而增大,然而在求解过 2598· 计算机应用研究 2017年 程中发现u的值越小算法运算时间越长.因为频繁通过反馈淘 方法[J,西安交通大学学报,2006,40(9):1041-1044 汰机制选择个体使计算复杂度增加,降低了算法运行速度。 [8 Zhang Luping, Wong T N. An objeet-coding genetic algorithm for in 虽然相关参数的变化会引起算法稳定性改变,但以上图表 tegrated process planning and scheduling [J. European Journal of Operational Research, 2015, 244(2 ): 434-444 显示最优解基本保持不变,表明算法的鲁棒性较好,不会因为[9]占盛坪,乔立红,工艺规划与左间调度及两者集成的研究現状和 某些参数的变化引起求解质量下降。 发展趋勢LJ」.计算机集成制造系统,2014,20(2):290-300. [10 Yu Mi Chen K 4结束语 nning and scheduling using a hybrid GA/PSO algorithm [J]. In national Journal of Advanced Manufacturing Technology 本文提出MG-HA算法求解PPS问题,探索种群中,使 2014,78(1):583-592 用混合遗传算法进行工艺链的更新,同吋基于聚类算法对加工[11高亮,李新宇.工艺观划与车间调度集成研究现状及进展打 顺序链进行聚类,然后计算可行解之间的海明距离进行淘汰 中国机械工程,2011,22(8):1001-1007 保证种群的差异性,最后结合差分进化算法更新加工顺序链。[12] Hackel s, Keidel J, Kehrer t. Organizational procedures for the inte 寻优种群屮,采用克隆领域搜索算法克隆适应度高的可行解并 gration of process planning and scheduling in Job-Shop manufacturing 通过领域搜索方式搜寻更优可行解,而且在克隆个体筛选时引 [C//Advances in Sustainable and Competitive Manufacturing Sys tems[S 1.: Springer International Publishing, 2013: 407-413 入反馈机制,避免了可行解的重复搜索,以最优种群的精英保 L13 Yang Y N, Parsaei II R, Leep I R. A prototype ofa feature-based 留策略保证算法收敛性。通过实例证明了 MG-HEA算法在求 lultiple-alternative process planning system with scheduling verifica- 解IPS问题时效果更好、效率更高。 tion[ J. Computers& Industrial Engineering, 2001, 39( 1-2) 参考文献 109-124 [1 Chryssolouris G, Chan S, Cobb W. Decision makingon the factory [14 Kim Y, Park K, Ko J. A symbiotic evolutionary algorithm for the inte- foor: an inlegraled approach Io process planning and scheduling gration of process planning and job shop scheduling J]. Computers Operations Research, 2003, 30(8): 1151-1171 Robotics and Computer Integrated Manufacturing, 1984, 1(3 4):315-319 [15]李新宇.工艺规划与车间调度集成问题的求解方法研究[D].武 [2 Rachelefsky G, Adelglass J, Corren J, et al. An approach for integra 汉:华中科技六学,2009 tion of process planning andschedulingl J]. International Journal of [16 Zhang Zhongwei, I'ang Renzhong, Peng ' lao, et al. A method for mini Computer Integrated Manufacturing, 2013, 277(22): 284-302 mizing the energy consumption of machining system: integration of [3 Lee H, Kim SS. Integration of process planning and scheduling using precess planning and scheduling[ J]. Journal of Cleaner Produc simulation based genetic algorithms [ J]. International Journal of ion,2016,137(11):1647-1662 Advanced Manufacturing Technology, 2001, 18(8): 586-590 [17 Petrovic M, Petronijevic J, Mitic M, et al. The ant lion optimization al 14 Kumar R, Tiwari M K, Shankar R. Scheduling of flexible manufactu orithm for integrated process planning and scheduling[ C]//Applied roach[ J. Pr roceedings Mechanics materials. 2016: 187-192 of the Institution of Mechanical engineers, Part B Journal of [18]王进峰,范孝良,宗鹏程,等.一种改进的蚁群算法在工艺规划与 Engineering Manufacture, 2003, 217(10): 1443-1453 车间调度集成优化中的应用[J].图学学报,2014,35(3):396- 5 Wan Liang, Li Xinyu, Gao Liang. A novel two-level genetic algorithm for integrated process planning and scheduling c/ Proc of IEEE In-「191乐赵勇,管在林,刘琼,等一种新调度关型及其在作业车间调度 ternational Conference on Systems, Man, and Cybernetics. Washington 口的应用[冂.机械工程学报,2008,44( DC: IEEE Computer Society, 2013: 2790-2725 [20] GuoY W, Li W D, Mileham A R, el al. Applicat ions of particle swarm 「6刘琦铀,施灿涛,李钬克,基于混合粒子群算法的工艺規划与调 optimization in integrated process planning and scheduling[ J]. Ro 度集成问题研究[J].工业工程与管理,2013,18(6):20-26. botics& Computer-Integrated Manufacturing, 2009, 25(2): 280 7]田颖,江平宇,周光辉,等,基于遗传算法的工竺规划与调度集成 288. (上接第2581页)影响。为了解决这一问题,提出了一种考虑 科学技术与工程,2013,13(5):1215-1218. CRPs间信任关系的云联盟算法,算法通过联盟博弈理论对多[6]朱匆,刘元君,彭自然,等移动云计算肀基于协作式溥弈模型 CRPs结盟进行了建模,使得全局信任度更高的CRP建立联 的资源分配方案[J].计算机应用研究,2014,31(3):912-916. 盟进行任务执行,并且得到最高的联盟成员收益。大量仿真实「71 Wei guiyi, Vasilakos A V, Xiong Naixue. Scheduling parallel cloud 验结果表明,算法产生的联盟结构不仅拥有最高的成员全局信 computing services: an evolutional game[ C]// Proc of the 1 st InteRna 任度和成员收益,符合 Pareto最优性质,并且联盟结构也是稳 tional Conference on Information Science and Engineering. 2009: 376 定的。 379. L8 Goii l, Guitart J, Torres J. Characterizing cloud federation for enhan 参考文献 cing providers'profit[ C]//Proc of IEEE International Conference on nao I ong oud computingand grid Co Cloud Computing. 2010: 123-130. puting 360-degree compared [C]//Proc of Grid Computing Environ ments Workshop. 2008: 1-10 L9」陈亚睿,田立勤,杨扬.云计算环境下基于动态博弈论的用户行 [2』颉斌,杨扬,钟泽伟.一科基于进化博弈论的云汁算虚拟计算资 为模型与分析[J.电子学报,2011,39(8):1818-1823 源配置模型J.北京交通大学学报,2013,37(5):75-79 「10]刘莹,罗永龙,乔云峰,等,云计算环境下基于行为预测的博弈 [3〗李陶深,张希翔.云计算下区分服务的演化埒弈调度算法[冂] 信任模型LJ」.小型徼型计算机系统,2015,36(10):2327-2333. 北京邮电大学学报,2013,36(1):41-46 [11 Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: a toolkit for [4」李卫平,武海燕,杨六。基于效益博弈的云计算资源动态可协调 modeling and simulation of cloud computing environments and evalua 分配策略研究[J计算机工程与科学,2016,38(1):57-61 tion of resource provisioning algorithms_I]. Software-Practice [5陶杰,吴小红,顾永跟.基于博弈的云计算任务分解研究[冂] Experience,2011,41(1):23-50