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 con￾straint satisfaction method SUN Shuhui‚XIA O Yongjun‚LI Tieke School of Economics and Management‚University of Science and Technology Beijing‚Beijing100083‚China ABSTRACT 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 收稿日期：2007-04-13 修回日期：2007-05-26 作者简介：孙树慧（1981—）‚女‚硕士研究生；李铁克（1958—）‚男‚ 教授‚博士生导师‚E-mail：tieke＠manage．ustb．edu．cn 面对日趋激烈的市场竞争和动态的客户需求环 境‚钢铁企业一方面为了满足客户小批量、多品种的 产品非均匀需求‚另一方面为了能够快速响应紧急 订单‚提高产品的及时交货能力‚通常会采用基于订 单（make to order‚MTO） 与 基 于 库 存 （make to stock‚MTS）的混合方式组织生产．在这种生产方 式下‚企业通常会产生相当数量的非订单库存产品 （以下称其为余材）．为了有效利用这些库存余材‚ 提高客户满足度、降低生产和库存成本‚需要将其与 客户订单进行合理的匹配．因此需要解决针对已知 的客户订单和库存余材集合‚以最大化订单满足率 和最小化匹配损失为目标‚在客户订单需求的约束 条件下‚选择库存产品并将其分派到客户订单的库 存匹配问题［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