基于约束满足方法求解热轧带钢库存匹配问题_约束管理_企业管理_2738

《基于约束满足方法求解热轧带钢库存匹配问题_约束管理_企业管理_2738》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于约束满足方法求解热轧带钢库存匹配问题_约束管理_企业管理   面对日趋激烈的市场竞争和动态的客户需求环境，钢铁企业一方面为了满足客户小批量、多品种的产品非均匀需求，另一方面为了能够快速响应紧急订单，提高产品的及时交货能力，通常会采用基于订单（maketoorder，MTO）与基于库存（maketostock，MTS）的混合方式组织生产。在这种生产方式下，企业通常会产生相当数量的非订单库存产品（以下称其为余材）。为了有效利用这些库存余材，提高客户满足度、降低生产和库存成本，需要将其与客户订单进行合理的匹配，因此需

2、要解决针对已知的客户订单和库存余材集合，以最大化订单满足率和最小化匹配损失为目标，在客户订单需求的约束条件下，选择库存产品并将其分派到客户订单的库存匹配问题。该问题可以抽象为具有NP难性质的多背包问题（multipleknapsackproblem，MKP）。   本文以钢铁企业生产管理中的库存匹配问题为对象，采用约束满足技术建立其数学模型并开发求解算法。约束满足是近年发展起来的一种源自人工智能领域、适用于组合优化问题建模与求解的新技术，该技术能以更加接近于现实世界的方式描述问题及其约束，在对问题的描述和求解方面具

3、有较好的灵活性。本文在对问题本质进行分析的基础上，将钢铁企业库存匹配问题映射为相应的约束满足问题，引入损失矩阵作为匹配损失的度量标尺，建立了该问题的约束满足模型，基于约束满足技术中的变量选择和值选择的思想，设计和开发面向实际应用的启发式算法。1问题描述及约束满足模型   1.1库存匹配问题描述   通常客户订单含有包括钢种、宽度、厚度、订货量等不同要求的内容，这种情况下可将订单拆分成具有相同钢种、宽度、厚度要求的子订单，本文将其称为订单项。针对某个订单项，按照钢卷的特征值建立一个满足该订单要求的钢卷集合，然后从中选

4、择匹配成本较低的钢卷组用于交付订单。实际的匹配工作通常不是针对单个订单而是面向整个订单池，因而增加了问题的复杂性。钢铁企业热轧带钢库存匹配问题的约束和目标可以描述如下。   （1）匹配集合中钢卷的钢种必须和订单项需求的钢种处在同一序列。在无法完全匹配的情况下，可以用较高级别的钢种“以好充次”匹配订单的低级别钢种需求，但要求保证钢种替代损失最小。为此引进钢种匹配损失矩阵P来度量单位质量钢种的匹配损失，定义损失矩阵P＝｛Pij︱i，j＝1，2，…，n｝，i表示待匹配钢卷的钢种，j表示订单要求的钢种，其中的元素表示如下：

5、       （2）匹配集合中钢卷的宽度和厚度要限制在订单项宽度和厚度需求限制范围，在不满足的情况下，要尽量减小匹配损失；   （3）充分利用现有余材，以达到充分降低库存的目的；   （4）考虑使尽可能多的订单项得到最大程度的满足。   通过对库存匹配问题的分析可知，库存匹配是在钢卷集合中找出满足所有约束的对象取值组合，实质上是一个有约束系统的求解问题，因此可以将库存匹配问题映射到约束满足问题（constraintsarisfactionproblem，CSP）。将库存匹配问题中的订单池和待选钢卷集映射为CSP中的

6、变量和域值，将库存匹配约束集合，包括订单要求的钢种、钢卷厚度、宽度等特征值约束映射为CSP中的约束集合，则库存匹配问题就转换为约束满足问题。   1.2符号及变量定义   为了便于描述模型，首先对符号和变量进行定义：i——订单编号，I为订单集合，i∈J；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）——

7、钢卷j具备的宽度；Ωi——特征值满足订单i要求的钢卷集合，ΩiJ；Ψj——钢钢卷j能够匹配的订单集合，ΨjI；ωi——实际匹配订单i的钢卷集合，ωiΩi。   1.3库存匹配问题约束满足模型   （1）问题目标       上式表示最大化与订单匹配的钢卷质量。   （2）问题约束       式（2）表示钢卷的钢种必须和订单要求钢种处在同一序列，且不低于订单要求；式（3）和（4）分别表示钢卷厚度、宽度与订单规定厚度、宽度差异不能超过某一范围，其中σ和λ分别代表实际生产对于厚度、宽度差异的规定；式（5）表示订单实际钢

8、卷匹配量不超过其订货量；式（6）表示每一份钢卷最多只能匹配给一份订单，ωi1和ωi2分别指匹配给订单i1和订单i2的钢卷集合；式（7）表示使尽可能多的订单得到最大程度的满足，其中α是评价指标的下界；式（8）表示最小化钢卷与订单匹配损失，β是评价指标的上界，pCG(i),SG(j)表东单位质量的钢卷与订单的钢种匹配惩罚函数。2CSP模型求解算法   约束满足问