论文研究-面向柔性工艺的作业车间调度问题混合遗传算法.pdf

所需积分/C币:9 2019-07-22 21:55:06 541KB .PDF
1
收藏 收藏
举报

针对离散制造业的许多产品采用柔性工艺设计增加作业计划调度的复杂性这一问题,对传统的FJSP进行了工序顺序柔性的扩展,将问题抽象为柔性工艺的作业车间调度问题(flexible process Job-Shop scheduling problem,FPJSP)。以缩短生产周期为目标,建立了该问题的整数规划模型,并设计了混合遗传算法。该算法针对FPJSP的特点设计了改进的遗传算法染色体编码方式和遗传算子,并结合变邻域搜索算法,设计了适合求解该问题的四种不同的邻域结构进行动态邻域搜索,以提高遗传算法的邻域搜索性能。通过应用实例验证了所提出的混合遗传算法在求解FPJSP的求解效率和优化性能方面的有效性
第5期 马雪丽,等:面向柔性工芑的作业车间调度问题混合遗传算法 1355 际的调度环境屮为具有柔性工艺特点的工件选择较优的工序3.1.3初始解构造 加工顺序和加工设备,并对所有工件的所有工序进行排序,确 为保证种群的多样性,种群的个休采用随机生成的方式产 定每台机器上加工工序的作业顺序。囚此,改进遗传算法的染生。染色体第一部分基因串的随机生成过程如下:对于柔性工 色体编码由以下两大部分组成:a)面向柔性工艺的编码,确定序顺序编码段,依次遍历各工件定义的柔性工序段,对类型为 含柔性工艺工件的工序顺序和工序的加工设备;b)基丁工序71和31的柔性工序段,只需随机生成活动工序的紧前工序的 顺序的编码,确定所有工件工艺路线上所有工序的加工顺序。序号,就可以确定该段柔性疗的顺序。若柔性序段T3(6 融合两种编码方式,形成条染色体,就可以得到面向柔性1〈6,10)〉,活动工序6的紧前工序序号可在15,7,8,9,10}集合 艺的作业车间调度问题的一个可行解。 内随机选择。假设随机选择的紧前工序序号为7,则该段柔性 1)面向柔性工艺的编码该部分的染色体又可以分为面工序的顺序为5,7,6,8,9,10,1l;对类型为T和T的柔性工 向工序顺序柔性的编码和面向机床选择柔性的编码两部分。序段,工序段内并列工序的加工顺序随机生成。 面向柔性工序顺序的染色体编码段表示所有包含柔性工 对丁机器柔性染色体编码段,依次遍历具有多个可选加工 序段工件的柔性工序的顺序方案。该部分的基囚串采用符号机器的T序,对于每个工序,从可选加T设备中选择一个设备 和自然数的混合编码表达方式。假设工件J包含S个柔性工在集合中的序号作为基因值。染色体第二部分基因串也采取 序段,且各柔性工序段的柔性工序的数量分别为1,,…,,随机生成的方式,每个工件号出现的次数等于其工序的总数。 则该部分基因串的长度L1可表示为 3.1.4选算子 L1=∑(:+∑1) 以最大完工时问最小作为FPSP的日标,对个休的适应度 进行评价,令 基因串可以表示为 Ob= max Ck,h∈(l,M) (8) 1,,…,O T0 7;:,…,7 Fi=Bmax -Ob (9) 其中:T表示(O,n,0,n)柔性工序段的类型,用符号表示,7∈其中:Obm表示种群中机器最大完工时间的最大值;Ob,表示 7,n2,7t,32;O.A,…,O、表示工件J某一柔性工序段中种群中个体i的机器最大完时间 柔性工序的加工顺序,用自然数表示。 设种群规模为N,则个体氵的适应度可以表示为 面向机器柔性的染色体编码段表示包含机床选择柔性工 f=F;/∑F (10) 疗的加设备方案。假设所有件中有多个可选加设各 序总数为fm,形成mn个可选加机器的子集分别为{S1 采用精英解保留策略与轮盘赌法相结合的选择方式,种群 S2,…,Sm},其中S表示第个有多个可选加工设备的工序的中近应度最大的染色体不参与交叉和变异直接复制到新种群, 可加工机器的集合,集合中可诜加工机器的个数为r表示为 新种群中的其他个体按照轮盘赌选择法从原种群中选择。 3.1.5交叉算子 ma,ma,m},则该部分染色体基因串的长度为m,表示为 针对染色体各段不同编码方式,设计三种不同的交又 g6m,第个基因g,为1,]内的整数,表示该位置基因箕子 所代表工序的加工机器为集合S中的第g;个元素m a)面向工序顺序柔性编码段的交叉。随机选定多个柔性 2)基于工序顺序的编码采用文献0]4提出的基于工工序段,选定的柔性工序段对应的染色体基囚进行互换。等位 序顺序的编码方式。各工序符号代表的工序序号由面向柔性基因交换后产生的染色体仍然是可行解。 工序顺序的染色体段解码后确定。 b)面向机器选择柔性编码段的交叉。采用单点交叉的方 3.1.2解码规则 式,对于选定的两个父体中的机器柔性编码段,随机选择个 解码时先对柒色体第一部分的基因串解码。首先对面问交叉点,将位于交又点之前的染色体基因进行交换。 柔性工序顺序的染色体段走行解码。对丁类型为们1和T2的 c)基于工序顺序编码段的交叉。采用部分匹配交叉方 柔性工序段,染色体中的基因序列郎代表其对应的工序段内柔 式 性工序的顺序。对T类型的柔性工序段,先根据Tn类型染3.1.6变异算子 色体的因序列确定该柔性工序段中上序的顺序,再根据其后 针对染色体各段不同的编码方式,设计三种不同的变异 类型为T2的基因序列对本段中部分柔性工序的顺序进行调算子 整。然后对面向机器柔性的染色体编码段进行解码,按染色体 a)面向柔性序顺序编码的基因段的变异。随机选中 中的基因值g,从该基因位置对应的机器选择柔性工序的可加个柔性工序段,若该柔性工序段的类型为71或T3,则在该段 工设备集合S中选择m作为该工序的加工机器,从而依次确自由工序的活动范围内随机生成自由工序的新的紧前工序号, 定具有机器柔性工序的加工设备。 就得到了该柔性工序段工序一个新的排列方式;若该柔性工序 付染色体第二鄙分的基因串解码时,按照由第部分星因段的类型为72或T2,采取逆转变异的方式,将该柔性工序段 串解码确定的各工件的工艺路线和各工序的加工设备,确定本内的基因值以逆向序列排列插入到原位置。 段基因串上基因对应的工序序号,依次将基因段上对应的各工 b)亩向机器柔性编码的基因段的变异。从编码段中选择 序按照最早允许加工时间插入到解码后指定的设备的空闲时个基因,杳找该基因对应的工什的工序,从该工序的可加工 间段,从而确定每台机器上加工工序的顺序,产生可行的调度设备集合屮随机选择一个设备编号,从而得到一个新的设备分 方案。若工件2的工艺路线为1,3,2,则表达式O1-O2102-配方案。 O31032-012-01.3-02,3中O2,2对应的工序序号为3,O23对应的 c)面向工序顺序编码的基因段的变异。采取逆转变异的 工序序号为2。 方式,随机选择一个基因段,将基因段中的基因值以逆向顺序 ·1356· 计算机应用研究 笃31卷 排列插入到原位置屮。 行N3邻域结构变换;若l=4,则对x进行N1邻域结构变换 3.2改进的变邻域搜索算法 (Gm=5);若l=5,则对x进行N,邻域结构变换(Gmx=5) 引入变邻域搜索算法的目的是通过当前解染色体某些基若1=6,则对x进行A4邻域结构变换。邻域结构变换后的解 因位值的改变,产牛邻近可行解,辯兔遗传进化过程的解陷入为x 局部最优。针对三种不同编码方式的染色体段.设计了四 d)若∫(x′)≤f(x),则x←x',保持不变,否则l←-l+1。若 种不同的邻域搜索结构构成邻域结构集来实现动态邻域搜索:1=7,则←1。←n+1 a)N1。采用多重swap移动邻域结构,通过相邻柒色体位 )若n<n灬,返回c);若n>n灬m,则←i+1。若i<la, 置基因的互换来改变基于柔性工序顺序的染色体编码段的基则返回b),含则执行f)。 因顺序,染色体其他部分的基因顺序保持不变。该邻域结构变 f)算汏终止,输出为x的最优解。 换的具体过程如下: 收进NS的整体流程如下: a)设置该邻域结构的最大迭代次数Gm,令G(1; setx←X,+1 b)随机选择柔性工序顺序编码段中的一个白然数类型 while i<I setn←1.l←1 的基因,判断该基囚位所在的柔性工序段的类型T while n n (c)若T2∈{T1,T31,且选中位置的基因的工序号并不是 if l=l the N,(x) (Gmax =3) 该柔性工序段内的活动工序,则将选中的基因作为该段内活动 L=2 then x'=N,(x)(Gmax=3) if l=3 then a'=N3( 工序的紧前工序;则,若该基因位之前的相邻基因的类型也 if l =4 then x'=N(x)(Gmax=5); 为自然数,则将两者进行交换,否则将选中位詈的基因与其后 if l=5 then x=N,(x (Gmx=5): 相邻位置的基因进行交换 if l=6 the (d)G←-G+1,若G>G灬,则邻域变换结束;否则返回步骤 end if if(x')≤f(x) then xex'; else l←l+1 b)N2。同样采用多重sw岬p移动邻域结构,改变工序顺序 编码的基因段中的基因顺序。其体的结构变换过程如下 if l=7 then l+-1 (a)设置该邻域结构的最大迭代次数G,令G←L n←n+1 (b)強机选择工序顺序编码段中的一个基因位,若该位置 end while 基因的工件号与其前面相邻基因位的工件号不同,则将两者进 i←i+1 行交换;否则将其与其后相邻基因位的基因进行互换 end while (c)G←G+1,若C>Gn、,则邻或变换结束;否则返回(b)。 c)N3。采用启发式规则改变基于机器柔性的编码段的机4仿真实验 器分配。随机选择机器柔性的染色体编码段的一个基因,判断 该位置基因所对应的件1序,从该1序可选加设备的集合 为了验证算法的寻优性能,首先采用文献17」中实验3 中诜择可最早加工该工序的设备作为该工序的加工机器。 的数据作为 FPJSP的实例数据进行对比。在文献[17中将工 d)NM。将两个工件所有工序对应的基因位置进行互換,艺中的工序顺序柔性拆解为多条工艺路线,并设计了A1GA 以改变基于工序顺序编码的基因段中的基因顺序。具体步骤( active learning genetic algorithm)求解。将本文设计的HGA与 如下 该文中的MLGA进行对比,采用与AGA相同的遗传参数,在 a)在基丁工序顺序的编码段中随机选择两个不同的工改进的vNs中令Nm=30,m=100HGCA计算10次得到的 件号 最优解为184s,算法的收敛过程如图1所示,算法确定的各工 (b)如果两个件的|序数量相等则将两个件的序的工艺路线如表1所示。HGA计算得到的调度方案如图2 在该染色体段中对应位置的基因从左至右依次互换,以产生邻所示。与文献[17]中AGA得到的最优解188s相比,得到了 域解;否则,将两者中工序数量较小的工件号从左至右依次与更进一步的优化。 工序数量较多的工件号进行互换,交换完成后产生邻域解。 基于以上四种邻域结构变换之后得到的染色休一定是可 行的谎度解。 以遗传算法的最优解作为ⅤNS的初始解x,以所有工件的 最大完工时间作为评价指标,评价函数为f(x),f(x)越小,则x 越接近最优解。结合以上四种邻域结构,改进的ⅤNS的流程 1.8 0102030405060708901 如下所示,具体过程如下 进化代数 a)将x作为邻域搜索过程的当前解x←x,构造邻域结构 图1HGA收敛过程由线 集N={N1,N2,N3,N4}。没置单次循环的最大邻域搜索次数 因该对比算例中屮没有给出算法的计算时间信息,所以为了 Nn3和最大循环代数la作为算法终止条件,令i1。 进一步地验证算法的稳定性和效率,结合文献[20]中的算例 b)令n+1,+1。 数据,构造了一系列的FPJP的实例,对文献17]中的ALGA c)若l=1,则对x进行N1邻域结构变换(Gms=3);若l=进行了实现,并对AGA和HCA的性能进行对比,比较结果如 2,则对x进行N2邻域结构变换(Cm=3);若l=3,则对x进表2所示。问题的复杂度用FPSP可行解搜索空间与JsP可 第5期 马雪丽,等:面向柔性工芑的作业车间调度问题混合遗传算法 1357 行解搜索空间的比例来描述。对于每一算例两组实验采用相参考文献 同的遗传参数,每个实验均在同一电脑上运行10次,采用算法 [I SAYGIN C, KILIC S E. Integrating flexible process plans with sche 求解时间、最优解、最优解平均值和最优解标准差四个参数对 uling in flexible manufacturing systems[ J I. International Journal 算法进行评价。从表2可以看出,对于不同规模的FP]SP, of Advanced Manufacturing Techonology, 1999, 15(4): 268-280 HGA的运算时间均要小于ALGA,且在大部分实例中得到的解 [2 BECK J C, FOX M S. Constraint-directed techniques for sched 要优于MIGA得到的解,最优解的标准差随 FPISP复杂度的降 alternative activities[ J. Artificial Intelligence, 2000, 121(1): 211 低而基今呈降低的趋势,可以进一步证明HGA求解FPSP的「31 BRUCKER P, SCHILIE R. Job-shop scheduling with multi-purpose 有效性和稳定性。 achines[ J. Computing, 1990, 45(4): 369-375 表1IGA确定的各工件的工艺路线 [41 GAO L, PENG C Y, ZHOL C, ct al. Solving flexible job-shop 件 工艺路线 件 工艺路线 cheduling problem using general particle swarm optimization C// Proc of the 36th International Conference on Computers Industrial 1-2-3-4-5-6-7-8 7-8-5-6-1-2-3-4 Engineering. 2006: 3018-3027 1-4-3-6-7-8 2-4-3-6-8 [5 SAIDI-MEHRABAD M, FATTAHI P. Flexible job shop scheduling 2-4-5-6-7-8 1-3-4-5-8 with tabu search algorithm[ J]. International Journal of Advanced 4-6-8-7 2-3-4-5-6-7-8 Manufacturing Technology, 2007, 32(5-6): 563-570 1-3-5-6-7 1 2-1-4-3-6-5-8-7 [6 LOUKIL T, TEGHEM J, FORTEMPS P. A multi-objective produc tion scheduling case study solved by simulated annealing J. Euro MM HH,3H出,44.3A5测 pean Journal of Operational Research, 2007, 179(3): 709-722 NN43,4,·,AAcg [7 CIOVANNI D L, PEZZELLA F. An improved genetic algorithm for 如M国H测图112.2]多和4区5酸中出 the distributed and flexible job-shop scheduling problem[ J].Euro M|2.141 2.5HNs.5 pean Joumal of Operational Research, 2010, 200(2): 395-408 最M,图,.图5 [8 AMIRI M, ZANDIEH M, YAZDANI M, et al. A variable neighbour M|5,1 ,x组注&b, 2,641,8 hood search algorithm for the flexible job-ghop scheduling problem [J. International Journal of Production Research, 2010, 48 时间 (19):5671-5689 图2HGA调度方案 [9 GAO Jie, SUN Lin-yan, GEN M. A hybrid genetic and variable 表2HGA和AIGA求解 FPJSP结果对比 neighborhood descent algorithm for flexible job shop scheduling prob- IGA求解FPSP ALGA求解FPsP lems[ J]. Computers Operations Research, 2008, 35(9): 2892 实复杂度 2907 例C 求解最优平均标准求解最优平均标准 时间s解/s值。差时间解/s值/s/s[10]宋莉波,徐学军,孙延明,等.一种求解柔性工作年间调度问题的 4.5231513151305.229151315130 混合遗传算法[J.管理科学学报,2010,13(11):49-5 23×203.7761290129004.522 12920 11 ZHANG Y F, SARAVANAN A \, FUH J Y H. Integration of process 34×333.455987987 04.2689879872.37 432x256.47324342436.72.87.138244724492.82 planning and scheduling by exploring the flexibility of process plan 53×274.44713321332.72.214.94213511351.63.26 ning[ J]. International Journal of Production Research, 2003 632×266.332212321266.36.82921392141.97.01 73×285.764150715105.09.26315331539.16.5 [12 JAIN A, JAIN P K, SINGH I P. An integrated scheme for process 83×2107.273227822866.897.83323092313.48.24 planning and scheduling in FMSL J. International Journal of Ad 932×289.386297729818.49.98730083014.29.3 vanced Manufacturing Technology, 2006, 30(11-12): 1111-1118 10 32 x210.659 2370 2377.9 6.87 9. 838 2396 2401.28.665 [13] OGUVEN C, OZBAKIR L, YAVUZ Y. Mathematical models for job 5632272280.26.48.25822892292.37.223 shop scheduling problems with routing and process plan flexibility 1232×2136.874215421595.77.82621682173.47. [J]. Applied Mathematical Modelling, 2010, 34(6): 1539-1548 13 32 x213.259 2272 2275 6.3 8. 132 2288 2291. 7 8. 43 [ 14] LI Xin-yu, SHAO Xin-yu, GAO Ling. Optimization of flexible 1433×2126.35619441944.66.57.48519551959.78.12 process planning by genetie programming[ J]. International Journal 1532×2169.567 of Advanced Manufacturing Technology, 2008, 38( 1-2): 143-153 16 3x222 11 579 3406 3400.2 8.23 13. 239 3431 3435.39.33 15] SHAO Xin-yu, LI Xin-yu, GAO L, et al. Integration of process plan 173×21216.67738703872.47.598.86539233904.49.025 ning and scheduling: a modified h l834×21817.568454145455.1619.61845684571.79.8 [J]. Computer Operations Research, 2009, 36(6): 2082-2096 19 37 x218.096 4020 4025.2 7.49 19.273 4035 4038 10.32 [16] LI Xin-yu, SHAO Xin-yu, GAO Ling, et al. An effective hybrid alge rithm for integrated proeess planning and scheduling[ J]. Internation- 5结束语 al Joumal of Production Economics, 2010, 126(2): 289-298 17] LI Xin-yu, GAO Ling, SHAO Xin-yu. An active learning genetic al 针对离散制造业产品柔性工艺设计中的工序顾序和机床 gorithm for integrated process planning and scheduling[J]. Expert 选择两类柔性,将传统的FJSP扩展为 FPJSP,综合利用遗传算 Systems with Applicatians, 2012, 39(8): 6683-6691 [18]张国辉,高亮,李培根,等.改进遗传算求解柔性作业车间调度 法全局寻优和ⅤNS算法邻域搜索能力较强的特点,设计∫混 问题[J.机械工程学报,2009,45(7):145-151 合遗传算法(HGA)对HS求解。实验结果表明,与现有研[19]潘全科,文宏,朱剑英,等基于粒子群优化和变邻域搜索的混 究中适用于求解FPSP的智能优化算法相比,本研究提出的 合调度算法[J]计算机集成制造系统,2007,13(2):323-328 HGA算法能够在较短的时间内综合考虑产品柔性工艺中的这 20]学文,马雪丽,曹德弼.τ序顺序柔性的作业车间调度问题的改 进遺传算法求解[冂].运筹与管理,2013,22(1):65-70 两类柔性,得到较优的作业计划调度方案,更适于求解具有21]09A01:Y9Hmgm0mm+ genetic alyorithm for in FPJSP特点的离散制造业作业计划调度问题。下一步工作将 tegrated pro ess planning and scheduling[ J]. International Journal 关注面向柔性工艺的多目标和动态调度问题。 of Advanced Manufacturing Technology, 2012, 58(5-8): 727-740

...展开详情
试读 5P 论文研究-面向柔性工艺的作业车间调度问题混合遗传算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841856 如果觉得有用,不妨留言支持一下
2019-07-22
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-面向柔性工艺的作业车间调度问题混合遗传算法.pdf 9积分/C币 立即下载
    1/5
    论文研究-面向柔性工艺的作业车间调度问题混合遗传算法.pdf第1页

    试读结束, 可继续读1页

    9积分/C币 立即下载 >