正在加载图片...
第10期 席阳等：针对固定重量板坯的板坯设计优化算法 ,1181, 51 =m则转入下一步； 01x11… (5)若j区m则令j=j+1,i=1并返回步骤 : (1),若=m则循环终止并输出结果 2.3第二阶段算法(MISW) 图1订单一板坯矩阵 本文将包含多个订单的板坯称为组合坯，而将 Fig.1 Order-slab matrix 定义2对于板坯j,称满足2=0：：≤， 仅包含一个订单的板坯称为整坯 当兰与不是0 r≥-1，Hi长0，Hj∈s的集合为板坯j的相容 的整数倍时，MNOS算法的结果中会出现多个订单 集合， 对于订单的宽度和重量需求为固定值的板坯设 组合在同一板坯内生产的情况，假定户，Q的 计问题，板坯数量最小和总盈余量最小是等价的，可 整数部分按整坯生产，小数部分按组合坯生产.由 转化为单目标优化问题进行求解：而对于订单的宽 于整坯已经不存在盈余量，故第二阶段的MTSW算 度和重量需求为区间值的板坯设计问题，无法简单 法仅需以组合坯（以下简称板坯）为对象，其目的是 地将两个优化目标统一起来，因此本文提出一种两 利用订单重量需求的柔性，使总盈余量最小， 阶段最优化算法MNOS-MTSW(minimizing the 为了便于算法描述，令月表示板坯j的盈余量 number of slabs and minimizing the total surplus (板坯j中没有订单对应的产量部分)，令©：表示订 weight),其中第一阶段将订单重量需求的下界作 单i可填补盈余的重量(g:=b:一a),令y时表示订 为目标重量，给出了板坯数量最小化的最优算法 单i在板坯j中的填补重量，令FS;表示板坯j最大 (MNOS):第二阶段利用订单重量需求的柔性，在保 可填补盈余的重量， 持板坯数量非增的限制下，给出了总盈余量最小化 根据上面的假设，针对MNOS算法得出的结 的最优算法(MTSW). 果，以下给出FS,的上界，并定义两个板坯盈余的填 2.2第一阶段算法(NOS) 补规则 文献[9]研究了考虑宽度区间值的组浇问题，其 性质1对Hi,j∈(1,2，，m),都有 方法可以用来求解第一阶段的板坯数量最小化问 月， 29:≥月 题.若把订单一板坯矩阵中的一个订单看作是一炉 钢水，一块板坯看作是一个浇次，并且用订单重量下 9 9:<月 界作目标重量，则可以将本阶段的问题转化为考虑 0∈0 宽度区间值的组浇问题，因此本文参照文献[9]算 填补规则1订单序号最小优先规则：优先用 法构造以下的MNOS算法，根据文献[9]的证明可 序号小的订单填补板坯中的盈余 知，MNOS算法是求解板坯数量最小的最优算法， 填补规则2板坯序号最小优先规则：优先填 [MNOS算法] 补序号小的板坯中的盈余， Step 1初步设定 根据以上两个填补规则，以性质1为贪婪准则， 令表示板坯j已分配所有订单的总重，置初 本文设计了一种在订单一板坯矩阵中从左向右、从 始g=0: 上到下依次填补组合坯盈余量的贪婪算法 令Pp:表示订单i未分配的重量，置初始p:= (MTSW),具体步骤如下. aii [MTSW算法] 令x表示订单分配在板坯中的重量，置初始 Step1初步设定 x前=0，=j=1,Hi,j∈(1,2，…，m); 由MNOS算法结果计算出x对，置初始月= 计算各板坯宽度区间的相容集合2 Step2重量分配 空0会g0g一4-a置初 Q (1)若订单0：∈n且p:0,那么当=j时令 始==1，i,j(1,2,,m) x=P:并转到步骤（③），否则转入下一步； Step2填补盈余 (2)令x=min qi/Q一gipi； ()若月>0且0：∈，则令y5=min{月， (3)更新q=g十xp:=p一x g,否则令y=0; (4)若<m则令=i+1并返回步骤(1)，若 (2)更新月=月一y9:=g:一yx=xg十S1 … S m O1 Om x11 … x1m ⋱ x m1 … x mm 图1 订单－板坯矩阵 Fig．1 Order-slab matrix 定义2 对于板坯 j称满足 Ωj＝｛Oi｜li≤ rj ri≥ rj－1∀ i∈ O∀ j∈ S｝的集合为板坯 j 的相容 集合． 对于订单的宽度和重量需求为固定值的板坯设 计问题板坯数量最小和总盈余量最小是等价的可 转化为单目标优化问题进行求解；而对于订单的宽 度和重量需求为区间值的板坯设计问题无法简单 地将两个优化目标统一起来因此本文提出一种两 阶段最优化算法 MNOS-MTSW （minimizing the number of slabs and minimizing the total surplus weight）．其中第一阶段将订单重量需求的下界作 为目标重量给出了板坯数量最小化的最优算法 （MNOS）；第二阶段利用订单重量需求的柔性在保 持板坯数量非增的限制下给出了总盈余量最小化 的最优算法（MTSW）． 2∙2 第一阶段算法（MNOS） 文献［9］研究了考虑宽度区间值的组浇问题其 方法可以用来求解第一阶段的板坯数量最小化问 题．若把订单－板坯矩阵中的一个订单看作是一炉 钢水一块板坯看作是一个浇次并且用订单重量下 界作目标重量则可以将本阶段的问题转化为考虑 宽度区间值的组浇问题．因此本文参照文献［9］算 法构造以下的 MNOS 算法．根据文献［9］的证明可 知MNOS 算法是求解板坯数量最小的最优算法． ［MNOS 算法］ Step1 初步设定 令 qj 表示板坯 j 已分配所有订单的总重置初 始 qj＝0； 令 pi 表示订单 i 未分配的重量置初始 pi＝ ai； 令 xij表示订单分配在板坯中的重量置初始 xij＝0i＝ j＝1∀ ij∈（12…m）； 计算各板坯宽度区间的相容集合 Ωj． Step2 重量分配 （1） 若订单 Oi∈Ωj 且 pi＞0那么当 i＝ j 时令 xij＝ pi 并转到步骤（3）否则转入下一步； （2） 令 xij＝min｛Q「qj／Q? －qjpi｝； （3） 更新 qj＝qj＋ xijpi＝ pi－ xij； （4） 若 i＜ m 则令 i＝ i＋1并返回步骤（1）若 i＝ m 则转入下一步； （5） 若 j＜ m 则令 j ＝ j ＋1i＝1并返回步骤 （1）若 j＝ m 则循环终止并输出结果． 2∙3 第二阶段算法（MTSW） 本文将包含多个订单的板坯称为组合坯而将 仅包含一个订单的板坯称为整坯．当 ∑ m i＝1 xij不是 Q 的整数倍时MNOS 算法的结果中会出现多个订单 组合在同一板坯内生产的情况假定 ∑ m i＝1 xij／Q 的 整数部分按整坯生产小数部分按组合坯生产．由 于整坯已经不存在盈余量故第二阶段的 MTSW 算 法仅需以组合坯（以下简称板坯）为对象其目的是 利用订单重量需求的柔性使总盈余量最小． 为了便于算法描述令 βj 表示板坯 j 的盈余量 （板坯 j 中没有订单对应的产量部分）令 δi 表示订 单 i 可填补盈余的重量（ gi＝ bi－ ai）令 yij表示订 单 i 在板坯 j 中的填补重量令 FS j 表示板坯 j 最大 可填补盈余的重量． 根据上面的假设针对 MNOS 算法得出的结 果以下给出 FS j 的上界并定义两个板坯盈余的填 补规则． 性质1 对∀ ij∈（12…m）都有 FS j＝ βj O∑i∈Ωj gi ≥ βj O∑i∈Ωj gi Q ∑i∈Ωj gi ＜ βj 填补规则1 订单序号最小优先规则：优先用 序号小的订单填补板坯中的盈余． 填补规则2 板坯序号最小优先规则：优先填 补序号小的板坯中的盈余． 根据以上两个填补规则以性质1为贪婪准则 本文设计了一种在订单－板坯矩阵中从左向右、从 上到 下 依 次 填 补 组 合 坯 盈 余 量 的 贪 婪 算 法 （MTSW）具体步骤如下． ［MTSW 算法］ Step1 初步设定 由 MNOS 算 法 结 果 计 算 出 xij 置 初 始βj ＝ Q ∑ m i＝1 xij／Q － ∑ m i＝1 xijyij＝0gi＝ bi－ ai置初 始 i＝ j＝1∀ ij∈（12…m）． Step2 填补盈余 （1） 若 βj ＞0且 Oi ∈Ωj则令 yij ＝min｛βj gi｝否则令 yij＝0； （2） 更新 βj＝βj－ yijgi＝ gi－ yijxij ＝ xij ＋ 第10期 席 阳等： 针对固定重量板坯的板坯设计优化算法 ·1181·