D0I:10.13374/i.issnl00It03.2008.06.025 第30卷第6期 北京科技大学学报 Vol.30 No.6 2008年6月 Journal of University of Science and Technology Beijing Jun.2008 基于约束满足方法求解热轧带钢库存匹配问题 孙树慧肖拥军李铁克 北京科技大学经济与管理学院，北京100083 摘要针对现代钢铁企业生产管理中的客户订单与热轧带钢库存产品的匹配问题，在考虑规格、质量、等级以及生产工艺 约束的基础上，建立了旨在最大化订单满足率且最小化匹配损失的约束满足模型.在对问题以及匹配对象特点进行分析的基 础上，引入匹配损失矩阵作为订单与库存余材属性匹配差异的损失惩罚，考虑到问题的复杂性，采用基于变量选择和值选择 的启发式算法求解模型的近优解，并通过数值实验对提出的算法进行了验证， 关键词热轧带钢：库存匹配：约束满足；启发式规则 分类号F406.2 Solving the inventory matching problem of hot rolling strips based on the con- straint satisfaction method SUN Shuhui,XIAO Yongjun,LI Tieke School of Economics and Management.University of Science and Technology Beijing.Beijing 100083,China ABSTRACI Aiming at maximizing the utilization of orders fulfillment and minimizing matching cost.a constraint satisfaction model was established for customer orders and the inventory matching problem of hot rolling strips in modern steel enterprise,considering steel specification.weight,grade,production process.and other constraints.Based on analyzing the characteristics of the problem and the matching objects,a matching loss matrix was introduced regarding as the loss penalty of the different matching result of or- ders and inventory surplus.Taking advantage of the complication of the issue,a heuristic algorithm.which is based on variable selec- tion and value selection,was presented to solve the model in sequence.Numerical experiment was given to validate the proposed algo- rithm. KEY WORDS hot rolling strip:inventory matching:constraint satisfaction:heuristic rule 面对日趋激烈的市场竞争和动态的客户需求环 条件下，选择库存产品并将其分派到客户订单的库 境，钢铁企业一方面为了满足客户小批量、多品种的 存匹配问题).该问题可以抽象为具有NP难性 产品非均匀需求，另一方面为了能够快速响应紧急 质的多背包问题3(multiple knapsack problem, 订单，提高产品的及时交货能力，通常会采用基于订 MKP). 单(make to order,MT0)与基于库存(make to 本文以钢铁企业生产管理中的库存匹配问题为 stok,MTS)的混合方式组织生产.在这种生产方 对象，采用约束满足技术]建立其数学模型并开 式下，企业通常会产生相当数量的非订单库存产品 发求解算法，约束满足是近年发展起来的一种源自 (以下称其为余材)·为了有效利用这些库存余材， 人工智能领域、适用于组合优化问题建模与求解的 提高客户满足度、降低生产和库存成本，需要将其与 新技术，该技术能以更加接近于现实世界的方式描 客户订单进行合理的匹配，因此需要解决针对已知 述问题及其约束，在对问题的描述和求解方面具有 的客户订单和库存余材集合，以最大化订单满足率 较好的灵活性0).本文在对问题本质进行分析的 基础上，将钢铁企业库存匹配问题映射为相应的约 和最小化匹配损失为目标，在客户订单需求的约束 束满足问题，引入损失矩阵作为匹配损失的度量标 收稿日期：2007-04-13修回日期：2007-05-26 尺，建立了该问题的约束满足模型，基于约束满足技 作者简介：孙树慧(1981一)女，硕士研究生：李铁克(1958一)，男， 术中的变量选择和值选择的思想，设计和开发面向 教授，博士生导师，E-mail:ticke@manage-ustb.edu.cn 实际应用的启发式算法
基于约束满足方法求解热轧带钢库存匹配问题 孙树慧 肖拥军 李铁克 北京科技大学经济与管理学院北京100083 摘 要 针对现代钢铁企业生产管理中的客户订单与热轧带钢库存产品的匹配问题在考虑规格、质量、等级以及生产工艺 约束的基础上建立了旨在最大化订单满足率且最小化匹配损失的约束满足模型．在对问题以及匹配对象特点进行分析的基 础上引入匹配损失矩阵作为订单与库存余材属性匹配差异的损失惩罚考虑到问题的复杂性采用基于变量选择和值选择 的启发式算法求解模型的近优解并通过数值实验对提出的算法进行了验证． 关键词 热轧带钢；库存匹配；约束满足；启发式规则 分类号 F406∙2 Solving the inventory matching problem of hot rolling strips based on the constraint satisfaction method SUN ShuhuiXIA O YongjunLI Tieke School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China ABSTRACT Aiming at maximizing the utilization of orders fulfillment and minimizing matching costa constraint satisfaction model was established for customer orders and the inventory matching problem of hot rolling strips in modern steel enterpriseconsidering steel specificationweightgradeproduction processand other constraints．Based on analyzing the characteristics of the problem and the matching objectsa matching loss matrix was introduced regarding as the loss penalty of the different matching result of orders and inventory surplus．Taking advantage of the complication of the issuea heuristic algorithmwhich is based on variable selection and value selectionwas presented to solve the model in sequence．Numerical experiment was given to validate the proposed algorithm． KEY WORDS hot rolling strip；inventory matching；constraint satisfaction；heuristic rule 收稿日期：2007-04-13 修回日期：2007-05-26 作者简介：孙树慧（1981—）女硕士研究生；李铁克（1958—）男 教授博士生导师E-mail：tieke＠manage．ustb．edu．cn 面对日趋激烈的市场竞争和动态的客户需求环 境钢铁企业一方面为了满足客户小批量、多品种的 产品非均匀需求另一方面为了能够快速响应紧急 订单提高产品的及时交货能力通常会采用基于订 单（make to orderMTO） 与 基 于 库 存 （make to stockMTS）的混合方式组织生产．在这种生产方 式下企业通常会产生相当数量的非订单库存产品 （以下称其为余材）．为了有效利用这些库存余材 提高客户满足度、降低生产和库存成本需要将其与 客户订单进行合理的匹配．因此需要解决针对已知 的客户订单和库存余材集合以最大化订单满足率 和最小化匹配损失为目标在客户订单需求的约束 条件下选择库存产品并将其分派到客户订单的库 存匹配问题［1—2］．该问题可以抽象为具有 NP 难性 质的多背包问题［3—6］ （multiple knapsack problem MKP）． 本文以钢铁企业生产管理中的库存匹配问题为 对象采用约束满足技术［7—8］ 建立其数学模型并开 发求解算法．约束满足是近年发展起来的一种源自 人工智能领域、适用于组合优化问题建模与求解的 新技术该技术能以更加接近于现实世界的方式描 述问题及其约束在对问题的描述和求解方面具有 较好的灵活性［9—10］．本文在对问题本质进行分析的 基础上将钢铁企业库存匹配问题映射为相应的约 束满足问题引入损失矩阵作为匹配损失的度量标 尺建立了该问题的约束满足模型基于约束满足技 术中的变量选择和值选择的思想设计和开发面向 实际应用的启发式算法． 第30卷 第6期 2008年 6月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．6 Jun．2008 DOI:10．13374／j．issn1001－053x．2008．06．025
第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·
.682 北京科技大学学报 第30卷 量选择和值选择的启发式算法求解模型 扫描订单1,2，…，|1，针对每一订单，遍历钢 2.1变量选择和值选择规则 卷信息，将满足订单约束的钢卷记录到订单匹配 (1)变量选择启发式规则，定义订单关键度鬥 集合2中，累计2：中钢卷质量，计算CR()值；同 CR()=∑m,/G,为变量选择指标，其中∑四，为 时将该订单记录到钢卷满足集合平中，累计钢卷 RUL(j)值： 特征值满足订单i约束的钢卷总质量 步骤3判断RUL值，若所有钢卷RUL值都 对CR()取值的分析： 为0则转步骤6；否则按RUL值从小到大将钢卷排 1°CR(i)=1说明匹配集合恰好满足订单 序，转步骤4. i,订单i最关键； 步骤4选择需匹配的订单：*， 2°CR()∈(1，∞)说明匹配集合2完全满足 1°若存在CR≥1的订单，根据CR(i)≥1且 订单i,CR(i)值越接近1说明订单i的可用值域越 小，相应订单越关键： CR(i)一1=nCR()一1选取订单*； 3°CR∈(0,1)说明匹配集合无法完全满足 2°若对所有的订单都有CR<1,则根据0< 订单i,必须放松约束条件，或安排生产计划，CR(i) CR(i*)<1且1一CR(i*)=mn1一CR(i)},选取 值越接近1说明与实际需求量越接近，订单i越 订单i; 关键 3°若对所有的订单都有CR=一1，意味着所有 以上三种状态中，订单关键程度的优先级依次 订单都被匹配过，处理结束，转步骤6； 降低，变量选择启发式要求选择最关键的订单进行 步骤5为订单i匹配钢卷. 库存匹配工作.满足当前订单、消耗库存的同时，其 1°若2·=0，则置CR(i)=一1，否则遍历 余待匹配订单的CR值也随之变化，需要重新计算， 步骤3产生的有序钢卷集合，逐一判断其是否存在 从而确定下一次循环需匹配的订单 于2·中，若不存在，继续下一个钢卷；否则，执行 (2)值选择启发式规则.定义钢卷对未匹配订 2° 单的资源需求度RUL(j)=|亚|为值选择指 2°判断i*已匹配钢卷质量与当前钢卷j*质量 标，其中平e代表钢卷j可以满足的未匹配订单集 之和是否超出G:',若超出，则置CR(i)=一1， 合. 并结束i对钢卷集合的遍历，转步骤3；否则转3°， RUL(j)取[1，I]范围内的整数值，值越小意 3°将记录到i*的实际匹配集合”中，置 味着钢卷j被其他未匹配订单选中的概率越小，所 RUL(G*)=0:遍历所有未匹配订单的匹配集合 以应优先选择满足min RUL()的钢卷分配给当前 2,将j从中去除；重新计算其他未匹配订单的CR 订单，其他钢卷供后续待匹配订单使用， 值，转步骤5. 2.2算法描述 步骤6算法结束 根据上述关于变量选择与值选择启发式规则的 算法的总体流程如图1所示. 讨论，可以将库存匹配CSP问题的求解过程具体描 3 述如下 数值实验 步骤1初始化 3.1计算举例 1°变量初始化：输入订单的编号i、需求钢种 表1和表2是从实际生产过程中抽取的部分测 CG(i)、需求钢卷宽度CW(i)、厚度CH()及订货 试数据，其中包括120个钢卷和6个订单.表1为 量G:; 客户订单信息，表2为钢卷统计信息，钢卷编号依次 2°值域初始化：输入库存钢卷的编号j、宽度 为Jo,h,,19,为了简明，本例中没有考虑钢种 SW(j)、厚度SH(j)及单位质量D; 匹配惩罚，并将钢卷宽度和厚度匹配需求简化为严 3°选择指标初始化： 格相等，算法用Visual C十十实现，程序运行的主要 置CR(i)=0,2=0,=1,…,1Il; 硬件环境为CPUP42.93GHz、RAM512MB,该测 置RUL(j)=0,Ψ=0，=1，…，1J; 试在1s内得出库存匹配结果，依据计算过程中选择 步骤2确定订单与钢卷的匹配关系，计算订 变量和值的先后顺序将匹配结果记录在表3中， 单CR初始值与钢卷RUL初始值
量选择和值选择的启发式算法求解模型． 2∙1 变量选择和值选择规则 （1） 变量选择启发式规则．定义订单关键度［9］ CR（ i）＝ ∑ j∈Ωi wj／Gi 为变量选择指标其中 ∑ j∈Ωi wj 为 特征值满足订单 i 约束的钢卷总质量． 对 CR（ i）取值的分析： 1°CR（ i）＝1说明匹配集合 Ωi 恰好满足订单 i订单 i 最关键； 2°CR（ i）∈（1∞）说明匹配集合 Ωi 完全满足 订单 iCR（ i）值越接近1说明订单 i 的可用值域越 小相应订单越关键； 3°CR∈（01）说明匹配集合 Ωi 无法完全满足 订单 i必须放松约束条件或安排生产计划CR（ i） 值越接近1说明 Ωi 与实际需求量越接近订单 i 越 关键． 以上三种状态中订单关键程度的优先级依次 降低变量选择启发式要求选择最关键的订单进行 库存匹配工作．满足当前订单、消耗库存的同时其 余待匹配订单的 CR 值也随之变化需要重新计算 从而确定下一次循环需匹配的订单． （2） 值选择启发式规则．定义钢卷对未匹配订 单的资源需求度［9］ RUL （ j ）＝｜Ψelse｜为值选择指 标其中 Ψelse代表钢卷 j 可以满足的未匹配订单集 合． RUL（ j）取［1｜I｜］范围内的整数值值越小意 味着钢卷 j 被其他未匹配订单选中的概率越小所 以应优先选择满足 min RUL（ j）的钢卷分配给当前 订单其他钢卷供后续待匹配订单使用． 2∙2 算法描述 根据上述关于变量选择与值选择启发式规则的 讨论可以将库存匹配 CSP 问题的求解过程具体描 述如下． 步骤1 初始化． 1°变量初始化：输入订单的编号 i、需求钢种 CG（ i）、需求钢卷宽度 CW（ i）、厚度 CH（ i）及订货 量 Gi； 2°值域初始化：输入库存钢卷的编号 j、宽度 SW（ j）、厚度 SH（ j）及单位质量 wj； 3°选择指标初始化： 置 CR（ i）∶＝0Ωi∶＝∅i＝1…｜I｜； 置 RUL（ j）∶＝0Ψj∶＝∅j＝1…｜J｜； 步骤2 确定订单与钢卷的匹配关系计算订 单 CR 初始值与钢卷 RUL 初始值． 扫描订单12…｜I｜针对每一订单遍历钢 卷信息将满足订单 i 约束的钢卷记录到订单匹配 集合Ωi 中累计 Ωi 中钢卷质量计算 CR（ i）值；同 时将该订单记录到钢卷满足集合 Ψj 中累计钢卷 RUL（ j）值； 步骤3 判断 RUL 值若所有钢卷 RUL 值都 为0则转步骤6；否则按 RUL 值从小到大将钢卷排 序转步骤4． 步骤4 选择需匹配的订单 i ∗． 1°若存在 CR≥1的订单根据 CR（ i ∗）≥1且 CR（ i ∗）—1＝min i∈ I ｛CR（ i）—1｝选取订单 i ∗； 2°若对所有的订单都有 CR＜1则根据0＜ CR（ i ∗）＜1且1—CR（ i ∗）＝min i∈ I ｛1—CR（ i）｝选取 订单 i ∗； 3°若对所有的订单都有 CR＝—1意味着所有 订单都被匹配过处理结束转步骤6； 步骤5 为订单 i ∗匹配钢卷． 1°若 Ωi ∗ ＝∅则置 CR（ i ∗）∶＝—1否则遍历 步骤3产生的有序钢卷集合逐一判断其是否存在 于 Ωi ∗ 中．若不存在继续下一个钢卷；否则执行 2°． 2°判断 i ∗已匹配钢卷质量与当前钢卷 j ∗质量 之和是否超出 Gi ∗．若超出则置 CR（ i ∗）∶＝—1 并结束 i ∗对钢卷集合的遍历转步骤3；否则转3°． 3°将 j ∗记录到 i ∗的实际匹配集合 ωi ∗ 中置 RUL（ j ∗）∶＝0；遍历所有未匹配订单的匹配集合 Ωi将 j ∗从中去除；重新计算其他未匹配订单的CR 值转步骤5． 步骤6 算法结束． 算法的总体流程如图1所示． 3 数值实验 3∙1 计算举例 表1和表2是从实际生产过程中抽取的部分测 试数据其中包括120个钢卷和6个订单．表1为 客户订单信息表2为钢卷统计信息钢卷编号依次 为 J0J1…J119．为了简明本例中没有考虑钢种 匹配惩罚并将钢卷宽度和厚度匹配需求简化为严 格相等．算法用 Visual C＋＋实现程序运行的主要 硬件环境为 CPU P42∙93GHz、RAM 512MB该测 试在1s 内得出库存匹配结果依据计算过程中选择 变量和值的先后顺序将匹配结果记录在表3中． ·682· 北 京 科 技 大 学 学 报 第30卷
第6期 孙树慧等：基于约束满足方法求解热轧带钢库存匹配问题 683 实规模的热轧带钢库存匹配问题，获得令人满意的 初始化变量，变量取值，选择指标 可行解 确定订单与钢卷的匹配关系， 表3匹配结果 计算订单CR值与钢卷RUL值 Table 3 Matching result of inventory 订单编号 匹配钢卷 匹配质量/： 接RUL值从小到大产生将钢卷排序 6 59,J58,57,J43,J41,J37,J3,Jh8 192 7 J83,52,Js:J31,J20,J7,5 161 选择当前待处理订单 J2,J80,J77,J76,J所，J0,J36,J21 192 选择匹配钢卷，更新其余订单Q值、 2 47,J44,J28,h6:J1,J8,2,h 190 CR值和钢卷RUL值 后 89,J69,J62,J61,J56,J39,J33,J29,J13 238 8,J70,J67,J65,J09,104,J96 185 所有订单处理完毕？ 3.2算法的有效性实验 Y 为了进一步地对算法的有效性进行验证，将本 输出结果，结束程序 文中提出的启发式算法与人工操作时便于计算的排 序搜索(largest first fit,LFF)规则进行比较， 图1算法总体流程图 LF℉算法的具体规则以及算法执行过程中的 Fig.1 Overall flowchart of the algorithm “以好充次”策略如下，(1)LFF规则：对所有的订单 表1订单信息 按其订货量由高到低进行优先度排序；对所有的库 Table 1 Information of custom orders 存余材按其质量由高到低进行优先度排序；按优先 订单编号 钢种 订单质量/h 规格/mm2 度由高到低选取订单，并按优先度由高到低选取可 Io SS330 200 1250×2.0 行的库存余材进行匹配.(2)在LFF算法的执行过 I1 SS400 180 1250×2.0 程中，进一步采用以下两种策略：策略A,允许“以好 I2 SS400 190 1280×2.5 充次”；策略B,不允许“以好充次” I3 SS490 200 1280×2.5 针对上述LF℉算法规则和两种执行策略，将其 I4 SS490 195 1250×2.0 与本文提出的启发式算法进行了比较实验。表4和 I5 SS490 240 1280×2.5 表5分别是针对随机生成的中等规模和大规模问 表2库存钢卷统计信息 题，关于计算时间、“以好充次”的比例以及得到完全 Table 2 Statistical information of inventory coils 匹配的订单质量等评价指标的数值实验结果 钢种 厚度/mm 宽度/mm 总质量 数量/卷 表4100卷余材10个订单的计算结果 SS330 1.2-2.3 1250 301 13 Table 4 Calculation result for 100 coils matching 10 orders SS330 2.34.3 1250 260 么 计算时 “以好充次“的 匹配合同 算法 SS330 2.34.3 1280 408 18 间/s 比例/% 总质量/ SS400 1.2-2.3 1250 235 1 本启发式算法 <1 S 1350 SS400 2.34.3 1250 280 12 LFF规则十策略A <1 40 1072 SS400 2.3~4.3 1280 418 18 LFF规则十策略B <1 0 606 SS490 1.2-2.3 1250 336 14 表51000卷余材100个订单的计算结果 SS490 2.34.3 1250 265 11 Table 5 Calculation result for 1000 coils matching 100 orders SS490 2.34.3 1280 324 12 计算时 “以好充次“的。 匹配合同 算法 间/s 比例/% 总质量h 约束满足的理论和方法能以更加接近现实世界 本启发式算法 25 23130 的方式描述本质上属于组合优化的复杂问题，基于 6 LFF规则十策略A 15 50 20637 约束满足技术开发的算法具有较高的运算效率，可 在有限的时间内求得问题的满意解.由本实例计算 LFF规则十策略B 15 0 16691 结果可以看出，该算法可以在较短的时间内解决现
图1 算法总体流程图 Fig．1 Overall flowchart of the algorithm 表1 订单信息 Table1 Information of custom orders 订单编号 钢种 订单质量／t 规格／mm 2 Ⅰ0 SS330 200 1250×2∙0 Ⅰ1 SS400 180 1250×2∙0 Ⅰ2 SS400 190 1280×2∙5 Ⅰ3 SS490 200 1280×2∙5 Ⅰ4 SS490 195 1250×2∙0 Ⅰ5 SS490 240 1280×2∙5 表2 库存钢卷统计信息 Table2 Statistical information of inventory coils 钢种 厚度／mm 宽度／mm 总质量／t 数量／卷 SS330 1∙2～2∙3 1250 301 13 SS330 2∙3～4∙3 1250 260 11 SS330 2∙3～4∙3 1280 408 18 SS400 1∙2～2∙3 1250 235 11 SS400 2∙3～4∙3 1250 280 12 SS400 2∙3～4∙3 1280 418 18 SS490 1∙2～2∙3 1250 336 14 SS490 2∙3～4∙3 1250 265 11 SS490 2∙3～4∙3 1280 324 12 约束满足的理论和方法能以更加接近现实世界 的方式描述本质上属于组合优化的复杂问题基于 约束满足技术开发的算法具有较高的运算效率可 在有限的时间内求得问题的满意解．由本实例计算 结果可以看出该算法可以在较短的时间内解决现 实规模的热轧带钢库存匹配问题获得令人满意的 可行解． 表3 匹配结果 Table3 Matching result of inventory 订单编号 匹配钢卷 匹配质量／t I′0 J59J58J57J43J41J37J34J18 192 I′1 J83J52J38J31J20J7J5 161 I′4 J92J80J77J76J66J50J36J21 192 I′2 J47J44J28J16J11J8J2J1 190 I′5 J89J69J62J61J56J39J33J29J13 238 I′3 J78J70J67J65J109J104J96 185 3∙2 算法的有效性实验 为了进一步地对算法的有效性进行验证将本 文中提出的启发式算法与人工操作时便于计算的排 序搜索（largest first fitLFF）规则进行比较． LFF 算法的具体规则以及算法执行过程中的 “以好充次”策略如下．（1）LFF 规则：对所有的订单 按其订货量由高到低进行优先度排序；对所有的库 存余材按其质量由高到低进行优先度排序；按优先 度由高到低选取订单并按优先度由高到低选取可 行的库存余材进行匹配．（2）在 LFF 算法的执行过 程中进一步采用以下两种策略：策略 A允许“以好 充次”；策略 B不允许“以好充次”． 针对上述 LFF 算法规则和两种执行策略将其 与本文提出的启发式算法进行了比较实验．表4和 表5分别是针对随机生成的中等规模和大规模问 题关于计算时间、“以好充次”的比例以及得到完全 匹配的订单质量等评价指标的数值实验结果． 表4 100卷余材10个订单的计算结果 Table4 Calculation result for100coils matching10orders 算法 计算时 间／s “以好充次”的 比例／％ 匹配合同 总质量／t 本启发式算法 ＜1 5 1350 LFF 规则＋策略 A ＜1 40 1072 LFF 规则＋策略 B ＜1 0 606 表5 1000卷余材100个订单的计算结果 Table5 Calculation result for1000coils matching100orders 算法 计算时 间／s “以好充次”的 比例／％ 匹配合同 总质量／t 本启发式算法 25 8 23130 LFF 规则＋策略 A 15 50 20637 LFF 规则＋策略 B 15 0 16691 第6期 孙树慧等： 基于约束满足方法求解热轧带钢库存匹配问题 ·683·
.684 北京科技大学学报 第30卷 通过上面的实验可以得到以下对比结果： factor.Syst Eng Theory Methodol Appl,2004.13(3):199 (1)与LF℉规则十策略A”的算法相比，本文 (胡琨元，陈文明，汪定伟，等.考虑批量因素的成品匹配与生 产计划联合优化系统工程理论方法应用，2004,13(3)： 提出的启发式算法虽然在匹配订单总质量方面略有 199) 逊色，但是在“以好充次”的比例方面有着非常明显 [2]Kalagnanam J R,Dawande M W,Trumbo M,et al.The surplus 的优势 inventory matching problem in the process industry.Oper Res, (2)与LFF规则十策略B”的算法相比，本文 2000,48:505 提出的启发式算法用少量的“以好充次”为代价，获 [3]Yan C L.Li T K,Zhang W X.Model and solution method for 得了在匹配订单总质量方面非常好的效果. inventory matching in hot milling strip production management Telecommun Eng Ind Eng:2004.44:245 (③)在计算时间方面，本文提出的启发式算法 (闫春丽，李铁克，张文新·热轧带钢生产管理中的库存匹配模 略逊于LF℉规则的算法，其原因在于在每次确定完 型.电讯技术：工业工程版，2004,44：245) 一个订单后，要对每块钢卷重新计算资源需求度 [4]Hu K Y.Zhu Y L.Wang D W.Adaptive PBIL algorithms for RUL值；并根据已经确定的钢卷重新计算剩余合同 order optimal matching problems.Syst Eng.2004.22(12):87 的订单关键度CR值，但本实验的结果表明，即使 (胡琨元，朱云龙，汪定伟.自适应PBL算法求解合同优化匹 配问题，系统工程，2004,22(12)：87) 对1000卷余材100个订单的大规模问题计算时间 [5]Hu K Y,Gao Z W,Wang D W.Optimal multi-objective model 也属于合理范围内，算法的计算效率是完全可以接 and algorithm for order matching problems in ironsteel plants. 受的 J Northeast Univ Nat Sci,2004,25(6):527 (胡琨元，高政威，汪定伟.钢铁企业合同匹配多目标优化模型 4结论 与算法.东北大学学报：自然科学版，2004,25(6)：527) [6]Wang Y.Cai Y,Li T K.ATP &CTP model in order planning 热轧带钢库存匹配是现代钢铁企业生产计划编 for iron &steel plants.Sci Technol Ind,2005.5(11):37 制前对客户订单预处理的关键问题之一，本文利用 (王字，蔡洋，李铁克.钢铁企业订单排产中的ATP与CTP模 近年来发展起来的约束满足方法求解库存匹配问 型.科技和产业，2005,5(11)：37) 题，建立了旨在最大化订单满足率且最小化匹配损 [7]Fromherz M P J.Constraint-based scheduling//American Con- 失的约束满足优化模型，并在此基础上设计了基于 trol Conference (ACC'01).Arlington.2001 [8]Sally C B,Chris N P,Barbara M S.Constraint satisfaction prob- 关键度的变量选择启发式和基于资源需求度的值选 lems:algorithms and applications.Eur J Oper Res,1999,119 择启发式算法，采用约束满足方法能够简洁、灵活 (3):557 地描述库存匹配问题，数据实验表明，本文提出的 [9]Min S S,Albert L.Yung J L.et al.Evaluation of ordering 启发式算法能够很好地求解热轧带钢库存匹配问 strategies for constraint satisfaction reactive scheduling.Decis 题，并具有能够应用于实际问题的计算效率， Support Syst,1998,22:187 [10]Guo D F,Li T K.Constraint satisfaction-based method for steel 参考文献 making continuous casting production scheduling problem.If Control,.2005,34(6):753 [1]Hu K Y.Chen W M.Wang D W.Research for joint optimization (郭冬芬，李铁克·基于约束满足方法求解炼钢一铸生产调度 of inventory matching and production planning considering mass 问题.信息与控制，2005,34(6)：753)
通过上面的实验可以得到以下对比结果： （1） 与“LFF 规则＋策略 A”的算法相比本文 提出的启发式算法虽然在匹配订单总质量方面略有 逊色但是在“以好充次”的比例方面有着非常明显 的优势． （2） 与“LFF 规则＋策略 B”的算法相比本文 提出的启发式算法用少量的“以好充次”为代价获 得了在匹配订单总质量方面非常好的效果． （3） 在计算时间方面本文提出的启发式算法 略逊于 LFF 规则的算法其原因在于在每次确定完 一个订单后要对每块钢卷重新计算资源需求度 RUL 值；并根据已经确定的钢卷重新计算剩余合同 的订单关键度 CR 值．但本实验的结果表明即使 对1000卷余材100个订单的大规模问题计算时间 也属于合理范围内算法的计算效率是完全可以接 受的． 4 结论 热轧带钢库存匹配是现代钢铁企业生产计划编 制前对客户订单预处理的关键问题之一．本文利用 近年来发展起来的约束满足方法求解库存匹配问 题建立了旨在最大化订单满足率且最小化匹配损 失的约束满足优化模型并在此基础上设计了基于 关键度的变量选择启发式和基于资源需求度的值选 择启发式算法．采用约束满足方法能够简洁、灵活 地描述库存匹配问题．数据实验表明本文提出的 启发式算法能够很好地求解热轧带钢库存匹配问 题并具有能够应用于实际问题的计算效率． 参 考 文 献 ［1］ Hu K YChen W MWang D W．Research for joint optimization of inventory matching and production planning considering mass factor．Syst Eng Theory Methodol Appl200413（3）：199 （胡琨元陈文明汪定伟等．考虑批量因素的成品匹配与生 产计划联合优化．系统工程理论方法应用200413（3）： 199） ［2］ Kalagnanam J RDawande M WTrumbo Met al．The surplus inventory matching problem in the process industry．Oper Res 200048：505 ［3］ Yan C LLi T KZhang W X．Model and solution method for inventory matching in hot milling strip production management． Telecommun Eng Ind Eng200444：245 （闫春丽李铁克张文新．热轧带钢生产管理中的库存匹配模 型．电讯技术：工业工程版200444：245） ［4］ Hu K YZhu Y LWang D W．Adaptive PBIL algorithms for order optimal matching problems．Syst Eng200422（12）：87 （胡琨元朱云龙汪定伟．自适应 PBIL 算法求解合同优化匹 配问题．系统工程200422（12）：87） ［5］ Hu K YGao Z WWang D W．Optimal mult-i objective model and algorithm for order matching problems in iron ＆ steel plants． J Northeast Univ Nat Sci200425（6）：527 （胡琨元高政威汪定伟．钢铁企业合同匹配多目标优化模型 与算法．东北大学学报：自然科学版200425（6）：527） ［6］ Wang YCai YLi T K．ATP ＆ CTP model in order planning for iron ＆ steel plants．Sci Technol Ind20055（11）：37 （王宇蔡洋李铁克．钢铁企业订单排产中的 ATP 与 CTP 模 型．科技和产业20055（11）：37） ［7］ Fromherz M P J．Constraint-based scheduling∥ A merican Control Conference （ ACC’01）．Arlington2001 ［8］ Sally C BChris N PBarbara M S．Constraint satisfaction problems：algorithms and applications．Eur J Oper Res1999119 （3）：557 ［9］ Min S SAlbert LYung J Let al．Evaluation of ordering strategies for constraint satisfaction reactive scheduling． Decis Support Syst199822：187 ［10］ Guo D FLi T K．Constraint satisfaction-based method for steel making-continuous casting production scheduling problem．Inf Control200534（6）：753 （郭冬芬李铁克．基于约束满足方法求解炼钢—铸生产调度 问题．信息与控制200534（6）：753） ·684· 北 京 科 技 大 学 学 报 第30卷