第8期 陈晓慧等：基于遗传算法的可重入钢管生产优化调度 。1069。 (3)每台机器同一时刻只能加工一个工件： 关系：式(8)表示一工件只能先加工完前一道次之后 (4)每个工件每道次在各个机器上的加工时间 才能进行下一道次加工，式(10)表示工序'贴在加 是确定的： 工站中有且仅有一台机器为其加工. (5)每个工件的可重入次数是确定的： (2)交货期满意度f2.随着产品生命周期的日 (6)每工件只有在加工完前一道次之后才能进 益缩短和客户需求水平的不断提高，企业对于准时 行下一道次加工： 交货的要求越来越高，产品的提前/拖期惩罚值也成 (7)在零时刻，所有的工件都可被加工. 为衡量系统调度性能的一个主要目标.基于图2轧 2钢管生产优化调度目标函数 批排序模型，工件W。的交货期窗口表示为[e, lo,其中e、l。分别为工件W。的最早和最晚交货 生产计划调度的目标包括基于加工完成时间的 期，当c<e,称工件W。提前；当ca>lo,称工件 指标、基于交货期的性能指标、基于库存的指标、基 W。拖期.如果工件在其交货期窗口内完工，则没有 于生产成本的指标以及综合性能指标等.考虑到钢 惩罚；否则不论工件W。提前或者拖期，都将对工件 管企业生产实际的需求，本文选择完成时间、交货期 W。的提前、拖期进行惩罚.总惩罚值f2可表示为： 满意程度和设备利用率三项指标建立多目标优化函 数.完成时间用工件的最后完工时间1度量，交货 f= 会ae+ase》 (12) 期满意度指标用提前/拖期(E/T)惩罚值f2度量， eo-Co Co<eo 设备利用率目标用机器总负荷f3度量.因此，多目 z1(co)= (13) 0 e≤c≤b 标调度优化的目标函数为： f(=minf1 (1) Co-lo co lo z2c)= (14) f(2=minf2 (2) 0 e≤co≤lo f(3到=minf3 (3) a1十a2=1 (15) (1)最后完工时间f.基于图2的轧批排序模 式中，a1、a2分别为工件W。的单位提前、拖期惩罚 型，现有N批待加工钢管.设工件W。第k道次在 权重，z1(c)、z2(co)分别为工件W。的提前、拖期 加工站上的加工工序记Vk:.最后完工时间f的 惩罚函数. 数学表达如下： (3)机器总负荷∫3.对一生产系统来说机器 f=max{co} (4) 是其重要的资源之一，机器的使用情况直接体现生 Co-XODT (5) 产系统的效率和效益.本文通过机器总负荷∫3的 约束条件如下： 情况来体现设备利用率目标. xaki一So贴=hai (6) f= (16) Xok!-hok1 Xoki;Vaki <Vokl (7) 6(k+i一k⊙0 (8) 空2unKe (17) xah≥hak,Hi其中，%ip=0或1 (9) 式(17)表示设备资源的有限性，任何一台设备的总 =1,P=1,29A 负荷都小于整个调度时长 (10) yahp=0或1,0=1,2，；N: 3基于Pareto遗传算法的模型求解 k=1,2,…D;i=L,2,,t;P=1,2,P: 针对轧批排序优化问题，需采用优化算法求解. (11) 常用的优化调度方法有多目标加权法、动态规划法、 式中，co是工件Wo的最后完工时间；saki、xaki和hak 局部搜索算法、交互式仿真方法以及遗传算法等. 是工序V:的开始时间、完成时间和处理时间；<表 对于遗传算法，Reeves9和Chen!1等通过对Fow 示了前后关系，Voi<Vk意味着Vak领先Vaki;如果 Shop调度研究结果表明，遗传算法优于模拟退火算 工件W。第k道次的第i工序分配给了对应加工站 法、邻近搜索算法和SPIRIT算法.文献I刂证明了 J下的第P台机器，则VakiP-=l;否则YakiPi=0. 遗传算法在可重入生产中具有优良的求解能力.进 式(6)和(9)表示工序'k:的开始时间、加工时 一步地，文献[I2-l3]研究了基于Pareto遗传算法 间和结束时间的关系，式(7)表示两工序之间的前后 的多目标优化方法，相比其他优化算法，该方法在收( 3) 每台机器同一时刻只能加工一个工件; ( 4) 每个工件每道次在各个机器上的加工时间 是确定的 ; ( 5) 每个工件的可重入次数是确定的; ( 6) 每工件只有在加工完前一道次之后才能进 行下一道次加工 ; ( 7) 在零时刻, 所有的工件都可被加工 . 2 钢管生产优化调度目标函数 生产计划调度的目标包括基于加工完成时间的 指标 、基于交货期的性能指标 、基于库存的指标 、基 于生产成本的指标以及综合性能指标等 .考虑到钢 管企业生产实际的需求, 本文选择完成时间、交货期 满意程度和设备利用率三项指标建立多目标优化函 数.完成时间用工件的最后完工时间 f 1 度量, 交货 期满意度指标用提前/拖期( E/T) 惩罚值 f 2 度量, 设备利用率目标用机器总负荷 f 3 度量 .因此, 多目 标调度优化的目标函数为 : f ( 1) =min f 1 ( 1) f ( 2) =min f 2 ( 2) f ( 3) =min f 3 ( 3) ( 1) 最后完工时间 f 1 .基于图 2 的轧批排序模 型, 现有 N 批待加工钢管.设工件 Wo 第k 道次在 Ji 加工站上的加工工序记 Vok i .最后完工时间 f 1 的 数学表达如下: f 1 =max{co} ( 4) co =x ODT ( 5) 约束条件如下: xok i -soki =hoki ( 6) xok l -hok l ≥xoki , Voki Vokl ( 7) so( k +1) i -soki >0 ( 8) xoki ≥hoki , i 其中, yokiP =0 或 1 ( 9) ∑ P i P =0 yokiP =1, P =1, 2, …, Pi ( 10) yokiP =0 或 1, o =1, 2, …, N ; k =1, 2, …, D ;i =1, 2, …, t ;P =1, 2, …, Pi ( 11) 式中, co 是工件 Wo 的最后完工时间 ;soki 、xok i和hoki 是工序 Voki的开始时间、完成时间和处理时间; 表 示了前后关系, Voki Vok l意味着 Vok l领先 Voki ;如果 工件 Wo 第k 道次的第i 工序分配给了对应加工站 Ji 下的第P 台机器, 则 yok iP =1 ;否则 yokiP =0 . 式( 6)和( 9)表示工序 Vok i的开始时间、加工时 间和结束时间的关系, 式( 7)表示两工序之间的前后 关系;式( 8) 表示一工件只能先加工完前一道次之后 才能进行下一道次加工, 式( 10)表示工序 Voki在加 工站Ji 中有且仅有一台机器为其加工. ( 2) 交货期满意度 f 2 .随着产品生命周期的日 益缩短和客户需求水平的不断提高, 企业对于准时 交货的要求越来越高, 产品的提前/拖期惩罚值也成 为衡量系统调度性能的一个主要目标.基于图 2 轧 批排序模型, 工件 Wo 的交货期窗口表示为[ eo, lo] , 其中 eo 、lo 分别为工件 Wo 的最早和最晚交货 期,当 co <eo, 称工件 Wo 提前;当 co >lo, 称工件 Wo 拖期 .如果工件在其交货期窗口内完工, 则没有 惩罚 ;否则不论工件 Wo 提前或者拖期, 都将对工件 Wo 的提前、拖期进行惩罚.总惩罚值 f 2 可表示为: f 2 = ∑ N o =1 ( a1 z 1( co) +a2 z 2( co)) ( 12) z 1( co) = eo -co co <eo 0 eo ≤co ≤lo ( 13) z 2( co) = co -lo co >lo 0 eo ≤co ≤lo ( 14) a1 +a2 =1 ( 15) 式中, a1 、a2 分别为工件 Wo 的单位提前、拖期惩罚 权重, z 1( co) 、z 2 ( co )分别为工件 Wo 的提前、拖期 惩罚函数. ( 3) 机器总负荷 f 3 .对一生产系统来说, 机器 是其重要的资源之一, 机器的使用情况直接体现生 产系统的效率和效益 .本文通过机器总负荷 f 3 的 情况来体现设备利用率目标 . f 3 = ∑ N o =0 ∑ D k =0 ∑ T i =0 ∑ P i P =0 hokiyokiP ( 16) ∑ N o =0 ∑ D k =0 hok iyokiP <max{co} ( 17) 式( 17)表示设备资源的有限性, 任何一台设备的总 负荷都小于整个调度时长. 3 基于 Pareto 遗传算法的模型求解 针对轧批排序优化问题, 需采用优化算法求解. 常用的优化调度方法有多目标加权法 、动态规划法、 局部搜索算法 、交互式仿真方法以及遗传算法等. 对于遗传算法, Reeves [ 9] 和 Chen [ 10] 等通过对 Flow Shop 调度研究结果表明, 遗传算法优于模拟退火算 法 、邻近搜索算法和SPIRIT 算法.文献[ 11] 证明了 遗传算法在可重入生产中具有优良的求解能力.进 一步地, 文献[ 12-13] 研究了基于 Pareto 遗传算法 的多目标优化方法, 相比其他优化算法, 该方法在收 第 8 期 陈晓慧等:基于遗传算法的可重入钢管生产优化调度 · 1069 ·