正在加载图片...
第6期 孙树慧等：基于约束满足方法求解热轧带钢库存匹配问题 .681. 1.2符号及变量定义 1问题描述及约束满足模型 为了便于描述模型，首先对符号和变量进行定 1.1库存匹配问题描述 义：一订单编号，1为订单集合，i∈I;一库存钢卷 通常客户订单含有包括钢种、宽度、厚度、订货 编号，J为库存钢卷集合，j∈J:G:一订单i的订货 量等不同要求的内容，这种情况下可将订单拆分成 量；0；一钢卷j的质量：CG(i)一订单i要求的钢 具有相同钢种、宽度、厚度要求的子订单，本文将其 种；SG(j)一钢卷j具备的钢种；CH(i)一订单i要 称为订单项，针对某个订单项，按照钢卷的特征值 求的厚度；SH(j)一钢卷j具备的厚度；CW(i)一订 建立一个满足该订单要求的钢卷集合，然后从中选 单i要求的宽度；SW()一钢卷j具备的宽度：n一 择匹配成本较低的钢卷组用于交付订单，实际的匹 特征值满足订单i要求的钢卷集合，Ω，二；平一钢 配工作通常不是针对单个订单而是面向整个订单 卷广能够匹配的订单集合，平二；，一实际匹配订 池，因而增加了问题的复杂性，钢铁企业热轧带钢 单i的钢卷集合，三n 库存匹配问题的约束和目标可以描述如下， 1.3库存匹配问题约束满足模型 (1)匹配集合中钢卷的钢种必须和订单项需求 (1)问题目标. 的钢种处在同一序列，在无法完全匹配的情况下， 可以用较高级别的钢种“以好充次”匹配订单的低级 =沿 (1) 别钢种需求，但要求保证钢种替代损失最小，为此 上式表示最大化与订单匹配的钢卷质量， 引进钢种匹配损失矩阵P来度量单位质量钢种的 (2)问题约束 匹配损失，定义损失矩阵P={p时i,j=1,2,…, SG(j)CG(i),Hj∈n,Hi∈1 (2) n},i表示待匹配钢卷的钢种，j表示订单要求的钢 abs(SH(j)-CH(i)≤o,Hj∈n,Hi∈I(3) 种，其中的元素表示如下： abs(SW(Gj)-CcW(i))≤λ，Hj∈n,Hi∈I(4) Py= 0 当=j时（同级钢种的钢卷匹配订单的 ∑m,≤G,∈，Hi∈I (5) j 匹配损失为0)； ,∩，=0，Hi1,i2∈，i1≠i2 (6) 当钢种为i的钢卷可以匹配钢种需求为 2 2G:- 乙☐0j >a (7) j的订单时（此时P表示钢种为i的 j 钢卷与钢种需求为j的订单匹配时的 (Po (8) 单位钢卷质量惩罚值)； 当钢种为i的钢卷不能与钢种需求 式(2)表示钢卷的钢种必须和订单要求钢种处 为j的订单匹配时， 在同一序列，且不低于订单要求：式（③）和(4)分别表 (2)匹配集合中钢卷的宽度和厚度要限制在订 示钢卷厚度、宽度与订单规定厚度、宽度差异不能超 单项宽度和厚度需求限制范围，在不满足的情况下， 过某一范围，其中ō和入分别代表实际生产对于厚 要尽量减小匹配损失； 度、宽度差异的规定；式(5)表示订单实际钢卷匹配 (③)充分利用现有余材，以达到充分降低库存 量不超过其订货量；式(6)表示每一份钢卷最多只能 的目的； 匹配给一份订单，，和心，分别指匹配给订单1和 (4)考虑使尽可能多的订单项得到最大程度的 订单2的钢卷集合；式(7)表示使尽可能多的订单 满足. 得到最大程度的满足，其中α是评价指标的下界； 通过对库存匹配问题的分析可知，库存匹配是 式（⑧）表示最小化钢卷与订单匹配损失，P是评价指 在钢卷集合中找出满足所有约束的对象取值组合， 标的上界，pcc(0,sc0)表示单位质量的钢卷与订单 实质上是一个有约束系统的求解问题，因此可以将 的钢种匹配惩罚函数 库存匹配问题映射到约束满足问题(constraint satis 2CSP模型求解算法 faction problem,CSP),将库存匹配问题中的订单 池和待选钢卷集映射为CSP中的变量和域值，将库 约束满足问题的求解是从变量的值域中寻找一 存匹配约束集合，包括订单要求的钢种、钢卷厚度、 致性的值分配给变量，满足所有的约束，基于库存 宽度等特征值约束映射为C$P中的约束集合，则库 匹配问题的特性，本文在求出各订单的可匹配集合 存匹配问题就转换为约束满足问题， :与各钢卷可满足的订单集合平的基础上采用变1 问题描述及约束满足模型 1∙1 库存匹配问题描述 通常客户订单含有包括钢种、宽度、厚度、订货 量等不同要求的内容这种情况下可将订单拆分成 具有相同钢种、宽度、厚度要求的子订单本文将其 称为订单项．针对某个订单项按照钢卷的特征值 建立一个满足该订单要求的钢卷集合然后从中选 择匹配成本较低的钢卷组用于交付订单．实际的匹 配工作通常不是针对单个订单而是面向整个订单 池因而增加了问题的复杂性．钢铁企业热轧带钢 库存匹配问题的约束和目标可以描述如下． （1） 匹配集合中钢卷的钢种必须和订单项需求 的钢种处在同一序列．在无法完全匹配的情况下 可以用较高级别的钢种“以好充次”匹配订单的低级 别钢种需求但要求保证钢种替代损失最小．为此 引进钢种匹配损失矩阵 P 来度量单位质量钢种的 匹配损失定义损失矩阵 P＝｛pij｜ij ＝12… n｝i 表示待匹配钢卷的钢种j 表示订单要求的钢 种其中的元素表示如下： pij＝ 0 当 i＝ j 时（同级钢种的钢卷匹配订单的 匹配损失为0）； pij 当钢种为 i 的钢卷可以匹配钢种需求为 j 的订单时（此时 pij表示钢种为 i 的 钢卷与钢种需求为 j 的订单匹配时的 单位钢卷质量惩罚值）； ∞ 当钢种为 i 的钢卷不能与钢种需求 为 j 的订单匹配时． （2） 匹配集合中钢卷的宽度和厚度要限制在订 单项宽度和厚度需求限制范围在不满足的情况下 要尽量减小匹配损失； （3） 充分利用现有余材以达到充分降低库存 的目的； （4） 考虑使尽可能多的订单项得到最大程度的 满足． 通过对库存匹配问题的分析可知库存匹配是 在钢卷集合中找出满足所有约束的对象取值组合 实质上是一个有约束系统的求解问题因此可以将 库存匹配问题映射到约束满足问题（constraint satisfaction problemCSP）．将库存匹配问题中的订单 池和待选钢卷集映射为 CSP 中的变量和域值将库 存匹配约束集合包括订单要求的钢种、钢卷厚度、 宽度等特征值约束映射为 CSP 中的约束集合则库 存匹配问题就转换为约束满足问题． 1∙2 符号及变量定义 为了便于描述模型首先对符号和变量进行定 义：i—订单编号I 为订单集合i∈ I；j—库存钢卷 编号J 为库存钢卷集合j∈ J；Gi—订单 i 的订货 量；wj—钢卷 j 的质量；CG（ i）—订单 i 要求的钢 种；SG（ j）—钢卷 j 具备的钢种；CH（ i）—订单 i 要 求的厚度；SH（ j）—钢卷 j 具备的厚度；CW（ i）—订 单 i 要求的宽度；SW（ j）—钢卷 j 具备的宽度；Ωi— 特征值满足订单 i 要求的钢卷集合Ωi⊆ J；Ψj—钢 卷 j 能够匹配的订单集合Ψj⊆ I；ωi—实际匹配订 单 i 的钢卷集合ωi⊆Ωi． 1∙3 库存匹配问题约束满足模型 （1） 问题目标． max F＝ ∑i∈ I∑ j∈ωi wj （1） 上式表示最大化与订单匹配的钢卷质量． （2） 问题约束． SG（ j）≥CG（ i）∀ j∈Ωi∀ i∈I （2） abs（SH（ j）—CH（ i））≤σ∀ j∈Ωi∀ i∈I （3） abs（SW（ j）—CW（ i））≤λ∀ j∈Ωi∀ i∈I （4） ∑ j∈ωi wj≤ Giωi⊆Ωi∀ i∈I （5） ωi1∩ωi2＝∅∀ i1i2∈Ii1≠ i2 （6） ∑i∈ I Gi— ∑ j∈ωi wj 2 ＞α （7） ∑i∈ I∑ j∈ωi （ pCG（ i）SG（ j） wj）＜β （8） 式（2）表示钢卷的钢种必须和订单要求钢种处 在同一序列且不低于订单要求；式（3）和（4）分别表 示钢卷厚度、宽度与订单规定厚度、宽度差异不能超 过某一范围其中 σ和λ分别代表实际生产对于厚 度、宽度差异的规定；式（5）表示订单实际钢卷匹配 量不超过其订货量；式（6）表示每一份钢卷最多只能 匹配给一份订单ωi1和 ωi2分别指匹配给订单 i1 和 订单 i2 的钢卷集合；式（7）表示使尽可能多的订单 得到最大程度的满足其中 α是评价指标的下界； 式（8）表示最小化钢卷与订单匹配损失β是评价指 标的上界pCG（ i）SG（ j）表示单位质量的钢卷与订单 的钢种匹配惩罚函数． 2 CSP 模型求解算法 约束满足问题的求解是从变量的值域中寻找一 致性的值分配给变量满足所有的约束．基于库存 匹配问题的特性本文在求出各订单的可匹配集合 Ωi 与各钢卷可满足的订单集合 Ψj 的基础上采用变 第6期 孙树慧等： 基于约束满足方法求解热轧带钢库存匹配问题 ·681·