D0I:10.13374/1.issnl00103.2008.10.005 第30卷第10期 北京科技大学学报 Vol.30 No.10 2008年10月 Journal of University of Science and Technology Beijing 0ct.2008 针对固定重量板坯的板坯设计优化算法 席 阳1,2) 李铁克) 1)北京科技大学经济管理学院，北京1000832)北京服装学院商学院，北京100029 摘要针对板坯重量被事先确定的情况，提出了客户订单重量需求规格和宽度需求规格为区间值的板坯设计问题，建立了 最小化板坯数量和总盈余量的多目标板坯设计模型.基于构建的订单一板坯矩阵和板坯相容集合，提出了一种两阶段的板坯 设计最优算法，算法的第一阶段实现板坯数量最小化，第二阶段实现总盈余量的最小化·针对提出的算法，给出了最优性质的 理论证明以及基于实际数据的应用算例 关键词客户订单；板坯设计：最优算法；区间值 分类号TP13 An optimal algorithm for slab designing of fixed weight slabs XI Yang2).LI Tieke) 1)School of Economics and Management,University of Science and Technology Beijing.Beijing 100083.China 2)Business School.Beijing Institute of Fashion Technology,Beijing 100029.China ABSTRACI A kind of slab designing problem was brought forward,in which the weight of slabs is fixed and the customer order de- mand specifications of weight and width are interval values.A multi-objective model to minimize the number of slabs and the total surplus weight was built.Based on the idea of the order"slab matrix and the compatible set of slabs,a two"stage optimal algorithm was proposed to solve the problem.In the algorithm.the first stage is to minimize the number of slabs,and the second stage is to minimize the total surplus weight.For this algorithm,the optimal nature was proved theoretically and an application case was given based on practical data. KEY WORDS customer order:slab designing:optimal algorithm:interval value 板坯设计(slab designing)是热轧带钢生产中连 对板坯设计策略进行以下的分析整理.在确定板坯 接客户需求与工艺要求的重要工作，是制定生产作 设计策略时通常需要考虑两方面的因素：一是需求 业计划的前提条件，随着市场需求的日益多样化和 规格的柔性程度，即客户订单需求的规格为定值还 具有柔性的先进生产设备的普及，大规模定制(mass 是区间值；二是设备的柔性程度，即在生产订单中的 customization)已经成为热轧带钢生产的主要发展方 板坯重量是固定的还是可变的，关于第一个因素， 向)]。作为实现大规模定制生产的关键环节，板 如果订单的需求规格是可以在一定范围调整的区间 坯设计已经成为热轧带钢生产管理中的重要课题， 值，则可利用此柔性来获得更好的板坯设计方案， 在热轧带钢生产组织过程中，一块板坯中可以 关于第二个因素，采用可变重量板坯的策略适合于 包括多个客户订单，一个客户订单也可以被分解到 多品种小批量的客户化生产方式：采用固定重量板 多个板坯中加工生产.板坯设计问题就是针对给定 坯的策略，适合于大规模定制的生产方式 的客户订单需求，在满足工艺限制的前提下设计出 针对客户订单的规格需求为固定值的情况，文 生产成本最低的板坯集合，其实质是组合优化问题， 献[3]研究了具有工艺路线约束和重量约束的板坯 迄今为止关于板坯设计问题的研究较少，本文首先 设计问题；文献[4]就此问题建立了板坯设计的三个 收稿日期：2007-10-09修回日期：2008-04-05 基金项目：国家自然科学基金资助项目(N。.70771008) 作者简介：席阳(1979一)，男，博士研究生；李铁克(1958一)，男，教授，博士生导师，Emai1l:tiekeli@163.com
针对固定重量板坯的板坯设计优化算法 席 阳12） 李铁克1） 1） 北京科技大学经济管理学院北京100083 2） 北京服装学院商学院北京100029 摘 要 针对板坯重量被事先确定的情况提出了客户订单重量需求规格和宽度需求规格为区间值的板坯设计问题建立了 最小化板坯数量和总盈余量的多目标板坯设计模型．基于构建的订单－板坯矩阵和板坯相容集合提出了一种两阶段的板坯 设计最优算法算法的第一阶段实现板坯数量最小化第二阶段实现总盈余量的最小化．针对提出的算法给出了最优性质的 理论证明以及基于实际数据的应用算例． 关键词 客户订单；板坯设计；最优算法；区间值 分类号 TP13 An optimal algorithm for slab designing of fixed weight slabs XI Y ang 12）LI Tieke 1） 1） School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China 2） Business SchoolBeijing Institute of Fashion TechnologyBeijing100029China ABSTRACT A kind of slab designing problem was brought forwardin which the weight of slabs is fixed and the customer order demand specifications of weight and width are interval values．A mult-i objective model to minimize the number of slabs and the total surplus weight was built．Based on the idea of the order-slab matrix and the compatible set of slabsa two-stage optimal algorithm was proposed to solve the problem．In the algorithmthe first stage is to minimize the number of slabsand the second stage is to minimize the total surplus weight．For this algorithmthe optimal nature was proved theoretically and an application case was given based on practical data． KEY WORDS customer order；slab designing；optimal algorithm；interval value 收稿日期：2007-10-09 修回日期：2008-04-05 基金项目：国家自然科学基金资助项目（No．70771008） 作者简介：席 阳（1979－）男博士研究生；李铁克（1958－）男教授博士生导师E-mail：tiekeli＠163．com 板坯设计（slab designing）是热轧带钢生产中连 接客户需求与工艺要求的重要工作是制定生产作 业计划的前提条件．随着市场需求的日益多样化和 具有柔性的先进生产设备的普及大规模定制（mass customization）已经成为热轧带钢生产的主要发展方 向［1－2］．作为实现大规模定制生产的关键环节板 坯设计已经成为热轧带钢生产管理中的重要课题． 在热轧带钢生产组织过程中一块板坯中可以 包括多个客户订单一个客户订单也可以被分解到 多个板坯中加工生产．板坯设计问题就是针对给定 的客户订单需求在满足工艺限制的前提下设计出 生产成本最低的板坯集合其实质是组合优化问题． 迄今为止关于板坯设计问题的研究较少本文首先 对板坯设计策略进行以下的分析整理．在确定板坯 设计策略时通常需要考虑两方面的因素：一是需求 规格的柔性程度即客户订单需求的规格为定值还 是区间值；二是设备的柔性程度即在生产订单中的 板坯重量是固定的还是可变的．关于第一个因素 如果订单的需求规格是可以在一定范围调整的区间 值则可利用此柔性来获得更好的板坯设计方案． 关于第二个因素采用可变重量板坯的策略适合于 多品种小批量的客户化生产方式；采用固定重量板 坯的策略适合于大规模定制的生产方式． 针对客户订单的规格需求为固定值的情况文 献［3］研究了具有工艺路线约束和重量约束的板坯 设计问题；文献［4］就此问题建立了板坯设计的三个 第30卷 第10期 2008年 10月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．10 Oct．2008 DOI:10．13374／j．issn1001－053x．2008．10．005
,1180 北京科技大学学报 第30卷 基本模型；文献[5]建立了板坯设计的整数规划模型 I:=[l,r:]一I表示订单i的宽度区间集合，l: (integer linear programming,ILP)和约束规划模型 和：分别表示最小和最大允许宽度：x一订单在 (constraint programming,CP),以及CP/ILP混合模 板坯类型j中生产的i的重量；Q一板坯的固定 型：文献[6]针对连铸设备生产能力不足的情况，研 重量；wd;一订单i在板坯宽度j内实际生产的宽 究了面向库存生产的板坯设计问题，针对客户订单 度「？一小于或等于A的整数，即下取整 的规格需求为区间值的情况，文献[7]以板坯数量和 1.3数学模型 盈余重量最小为优化目标，以可变重量板坯为对象 以下给出考虑订单宽度和重量需求为区间值约 提出了考虑客户订单重量需求为区间值的板坯设计 束，面向大规模定制生产的固定重量板坯设计多目 模型和求解方法；文献[8]在板坯大小可以任意切割 标优化模型P: 的前提下，针对客户订单对板坯宽度和重量的需求 都为区间值的情况，提出了以板坯数量最小和总交 min F1- (1) 货重量最大为目标的板坯设计模型和启发式算法， 在热轧带钢生产中对具有多样性的客户订单进 min F2- 行合理地组合、形成相对标准的生产订单，是实现大 规模定制的主要途径.因此本文在上述己有研究成 0≤空g≤0.Vjs (3) 果的基础上，以固定重量板坯为对象，针对客户订单 对板坯宽度和重量的需求都为区间值的情况，建立 a空与5V0 (4) 板坯设计模型并开发优化算法， l,≤wd≤ri,Hi∈0，Hj∈s (5) (6) 1问题描述及数学模型 wdg=wdj,Hu,v∈0,1.∩ln≠0 Hxja,b,∈Z (7) 1.1问题概述 Hl,Tiwd∈Z (8) 一般而言，板坯设计问题中存在着钢种、重量、 目标函数(1)为最小化板坯数量；目标函数(2) 宽度、厚度、交货期等方面的约束，本文重点考虑其 为最小化板坯的总盈余量：约束（③）表示所有订单分 中的重量和宽度约束，并把以下的讨论界定在给定 配在某一板坯中的重量之和不能超过板坯允许的重 的客户订单集合能够符合其他约束的范围之内，这 量范围；约束(4)表示需满足的订单重量区间限制； 里作如下假设：(1)客户订单对总重量的需求是由最 约束(5)表示需满足的订单宽度区间限制；约束(6) 大和最小重量组成的区间值：（②）客户订单对板坯宽 表示组合在同一板坯内任意订单需有相同的宽度区 度的需求是由最大和最小宽度组成的区间值；(3)假 间：约束(7)和(8)为变量的取值范围 设对某一类产品来说，板坯的重量是一个固定值， 模型P是一个多目标优化问题，解决多目标优 在客户订单转化为板坯的过程中，客户订单和 化的常用方法是利用加权平均、极大极小算子等，将 板坯之间可以是多对多的关系，多个订单能放入同 原问题转换为单目标问题后求解，但一般只能得到 一板坯的必要条件是该板坯宽度能满足所有这些订 原问题的非劣解。本文利用对象问题的特殊性质， 单的宽度需求，并且总重不超出相应板坯的重量限 提出以下的两阶段板坯设计优化算法， 制，本文考虑的板坯设计问题是在满足客户订单的 前提下，利用客户订单对宽度和重量需求的柔性优 2最优算法 化板坯组合，其目标为：(1)板坯总数量最小；(2)板 2.1算法的基本思想 坯的总盈余量（板坯中没有订单对应的产量部分的 为了分析给出的模型，本文提出以下定义 总和)最少 定义1称将订单的最大允许宽度：按非减排 1.2符号定义 序（令ro=0),以宽度区间为[r-1,r:]的板坯序号 为了便于描述，模型中用到的符号和变量定义 j为列向量（令j与确定其宽度区间r:的订单序号i 如下：一订单序号，0为所有订单集合，∈0， 一致)，以订单序号i为行向量，以x为元素的矩阵 设共有m个订单；一板坯序号（对应一类板坯宽 为订单板坯矩阵， 度区间)，S为所有板坯类型集合，j∈S,设共有 按照定义1构造的mXm阶订单-板坯矩阵X n类板坯；G:=[a,b:]一Gi表示订单i的重量区 (如图1所示)，可以表示板坯设计问题的解（实际生 间集合，：和b:分别表示最小和最大允许重量； 产中wd取[r-1,r]的均值即可)
基本模型；文献［5］建立了板坯设计的整数规划模型 （integer linear programmingILP）和约束规划模型 （constraint programmingCP）以及CP／ILP 混合模 型；文献［6］针对连铸设备生产能力不足的情况研 究了面向库存生产的板坯设计问题．针对客户订单 的规格需求为区间值的情况文献［7］以板坯数量和 盈余重量最小为优化目标以可变重量板坯为对象 提出了考虑客户订单重量需求为区间值的板坯设计 模型和求解方法；文献［8］在板坯大小可以任意切割 的前提下针对客户订单对板坯宽度和重量的需求 都为区间值的情况提出了以板坯数量最小和总交 货重量最大为目标的板坯设计模型和启发式算法． 在热轧带钢生产中对具有多样性的客户订单进 行合理地组合、形成相对标准的生产订单是实现大 规模定制的主要途径．因此本文在上述已有研究成 果的基础上以固定重量板坯为对象针对客户订单 对板坯宽度和重量的需求都为区间值的情况建立 板坯设计模型并开发优化算法． 1 问题描述及数学模型 1∙1 问题概述 一般而言板坯设计问题中存在着钢种、重量、 宽度、厚度、交货期等方面的约束．本文重点考虑其 中的重量和宽度约束并把以下的讨论界定在给定 的客户订单集合能够符合其他约束的范围之内．这 里作如下假设：（1）客户订单对总重量的需求是由最 大和最小重量组成的区间值；（2）客户订单对板坯宽 度的需求是由最大和最小宽度组成的区间值；（3）假 设对某一类产品来说板坯的重量是一个固定值． 在客户订单转化为板坯的过程中客户订单和 板坯之间可以是多对多的关系多个订单能放入同 一板坯的必要条件是该板坯宽度能满足所有这些订 单的宽度需求并且总重不超出相应板坯的重量限 制．本文考虑的板坯设计问题是在满足客户订单的 前提下利用客户订单对宽度和重量需求的柔性优 化板坯组合其目标为：（1）板坯总数量最小；（2）板 坯的总盈余量（板坯中没有订单对应的产量部分的 总和）最少． 1∙2 符号定义 为了便于描述模型中用到的符号和变量定义 如下：i———订单序号O 为所有订单集合i∈ O 设共有 m 个订单；j———板坯序号（对应一类板坯宽 度区间）S 为所有板坯类型集合j ∈ S设共有 n 类板坯；Gi＝［ aibi］－－－ Gi 表示订单 i 的重量区 间集合ai 和 bi 分别表示最小和最大允许重量； Ii＝［ liri ］－－－Ii 表示订单 i 的宽度区间集合li 和 ri 分别表示最小和最大允许宽度；xij———订单在 板坯类型 j 中生产的 i 的重量；Q———板坯的固定 重量；wd ij———订单 i 在板坯宽度 j 内实际生产的宽 度；「A? ———小于或等于 A 的整数即下取整． 1∙3 数学模型 以下给出考虑订单宽度和重量需求为区间值约 束面向大规模定制生产的固定重量板坯设计多目 标优化模型 P： minF1＝ ∑ n j＝1 ∑ m i＝1 xij／Q （1） minF2＝ ∑ n j＝1 Q ∑ m i＝1 xij／Q － ∑ n j＝1 ∑ m i＝1 xij （2） s．t 0≤ ∑ m i＝1 xij≤ Q∀ j∈S （3） ai≤ ∑ n j＝1 xij≤bi∀ i∈ O （4） li≤wd ij≤ ri∀ i∈ O∀ j∈S （5） wd uj＝wdvj∀ uv∈ OIu∩Iv≠／○ （6） ∀ xijaibi∈Z ＋ （7） ∀ liriwd ij∈Z ＋ （8） 目标函数（1）为最小化板坯数量；目标函数（2） 为最小化板坯的总盈余量；约束（3）表示所有订单分 配在某一板坯中的重量之和不能超过板坯允许的重 量范围；约束（4）表示需满足的订单重量区间限制； 约束（5）表示需满足的订单宽度区间限制；约束（6） 表示组合在同一板坯内任意订单需有相同的宽度区 间；约束（7）和（8）为变量的取值范围． 模型 P 是一个多目标优化问题解决多目标优 化的常用方法是利用加权平均、极大极小算子等将 原问题转换为单目标问题后求解但一般只能得到 原问题的非劣解．本文利用对象问题的特殊性质 提出以下的两阶段板坯设计优化算法． 2 最优算法 2∙1 算法的基本思想 为了分析给出的模型本文提出以下定义． 定义1 称将订单的最大允许宽度 ri 按非减排 序（令 r0＝0）以宽度区间为［ ri－1ri ］的板坯序号 j 为列向量（令 j 与确定其宽度区间 ri 的订单序号 i 一致）以订单序号 i 为行向量以 xij为元素的矩阵 为订单－板坯矩阵． 按照定义1构造的 m× m 阶订单－板坯矩阵 X （如图1所示）可以表示板坯设计问题的解（实际生 产中 wd ij取［ ri－1ri］的均值即可）． ·1180· 北 京 科 技 大 学 学 报 第30卷
第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：∈，则令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·
.1182 北京科技大学学报 第30卷 y若月=0则转到步骤(4)，否则转入下一步： 计问题的最优算法，其时间复杂性为O(m2) (3)若j和k≤j 可以得到如图2所示的最小化板坯数量的最优解， 的两种情况.当k>j时，MTSW算法保证了板坯j 订单板坯矩阵中的元素表示订单在对应宽度区间 的盈余不能由序号较大的板坯k(k>)进行移位填 内需要加工组合坯的重量，括号中的数字表示对应 补，当k≤时，假设移位量为y,来自剩余量的填 订单在该宽度区间内需要加工的整坯的数量， 补量为g:>0,则：(1)当0,则必定有9：=0， 订单 1290130013651430145015801580163017801800 与假设矛盾：(2)当i≥i时，根据定义1，有：'≥ 1 12(3) r,又因为板坯j接受的移位量为y,说明0：∈n, 1621(3) 3 有：≥-1，则≥：≥-1，另由于0：∈ 1 24(8) 4 20(2) D(g:'填入板坯k中)，有：≤rk,又因为此时k≤ 82(5) j,根据定义1有≥rk,则L:≤rk≤)，故根据定 6 8(4) 义2可知0：∈口，说明填补量9：也可以填补板 2024(2) 坯的盈余，根据第一种可能分析，这种情况不存 4 16(10 在，因此，第二种可能也不存在， 9 20(5) 综合以上针对两种可能的分析，可知不存在针 10 824(6) 对当前盈余的可填补量，以使目标值减小，因此与初 始假设相矛盾；此外，在证明的过程中，板坯数量不 图2区间值板坯设计MNOS算法结果 会增加，故原命题成立 Fig.2 Results of MNOS algorithm of interval value slab designing 证毕 针对由MNOS算法产生的有盈余的组合坯 由于MTSW算法是建立在MNOS算法的结果 (图2中第3、5、8、10列)，应用MTSW算法实现盈 之上，且没有增加板坯数量，因此本文提出的两阶段 余量的最优，计算过程如图3所示（图3中，第一行 算法是解决基于固定重量的带区间值约束的板坯设 的数字表示板坯号，各个矩形阴影中数字表示订单
yij若 βj＝0则转到步骤（4）否则转入下一步； （3） 若 i＜ m 则令 i＝ i＋1并返回步骤（1）若 i＝ m 则转入下一步； （4） 若 j＜ m 则令 j ＝ j ＋1i＝1并返回步骤 （1）若 j＝ m 则循环终止并输出结果． 定理1 上述 MTSW 算法在板坯数量不变的 前提下给出了总盈余量最小化的最优解． 证明 用反正法．假设 MTSW 算法给出的解 不是最优解则说明还有盈余可以进一步填补这只 有两种可能：第一种可能是当前盈余仍可以由剩余 量 未分配到板坯中的重量 ∑ m i＝1 bi－ ∑ m i＝1 ∑ m j＝1 xij 填 补；第二种可能是可以通过移位填补（即把已经分配 到某个板坯 k 中的一部分重量移动到另一个板坯 j）对现有分配方案进行改变并且可以由剩余量填 补新产生的盈余． 针对上述第一种可能由于 MTSW 算法是从左 向右、从上到下依次将 gi（ Oi∈Ωj）填入板坯 j 中 直到板坯 j 被填满或仅剩无法填补的盈余时才进 行下一板坯的填补因此不会出现板坯 j 中有可填 补的盈余而没有被填补的情况故第一种可能不存 在． 针对上述第二种可能可以分为 k＞ j 和 k≤ j 的两种情况．当 k＞ j 时MTSW 算法保证了板坯 j 的盈余不能由序号较大的板坯 k（ k＞ j）进行移位填 补．当 k≤ j 时假设移位量为 yik来自剩余量的填 补量为 g i ∗ ＞0则：（1） 当 i ∗ ＜ i 时根据 MTSW 算法若 OiOi ∗ ∈Ωk 且 yik＞0则必定有 gi ∗ ＝0 与假设矛盾；（2）当 i ∗≥ i 时根据定义1有 ri ∗ ≥ ri又因为板坯 j 接受的移位量为 yik说明 Oi∈Ωj 有 ri ≥ rj－1则 ri ∗ ≥ ri ≥ rj－1另 由 于 Oi ∗∈ Ωk（ gi ∗填入板坯 k 中）有 li ∗≤ rk又因为此时 k≤ j根据定义1有 rj≥ rk则 li ∗ ≤ rk≤ rj故根据定 义2可知 Oi ∗ ∈Ωj说明填补量 gi ∗ 也可以填补板 坯 j 的盈余根据第一种可能分析这种情况不存 在．因此第二种可能也不存在． 综合以上针对两种可能的分析可知不存在针 对当前盈余的可填补量以使目标值减小因此与初 始假设相矛盾；此外在证明的过程中板坯数量不 会增加故原命题成立． 证毕． 由于 MTSW 算法是建立在 MNOS 算法的结果 之上且没有增加板坯数量因此本文提出的两阶段 算法是解决基于固定重量的带区间值约束的板坯设 计问题的最优算法其时间复杂性为 O（ m 2）． 3 算例 从某大型钢厂的生产实际中按板坯设计模型要 求随机选取10个订单（如表1）表中最后两列为对 应订单的宽度和重量的定值需求以便和区间值模 型进行对比分析． 表1 生产订单数据 Table1 Order information 订单序号 li ri ai bi Ii Gi 1 1230 1290 96 100 1260 98 2 1255 1300 121 130 1278 126 3 1300 1365 255 270 1333 263 4 1385 1430 76 80 1408 78 5 1395 1450 150 160 1423 155 6 1510 1580 120 128 1545 124 7 1550 1580 100 105 1565 103 8 1560 1630 300 320 1595 310 9 1750 1780 160 175 1765 168 10 1780 1800 200 212 1790 206 根据生产实际取参数 Q＝28t由 MNOS 算法 可以得到如图2所示的最小化板坯数量的最优解 订单－板坯矩阵中的元素表示订单在对应宽度区间 内需要加工组合坯的重量括号中的数字表示对应 订单在该宽度区间内需要加工的整坯的数量． 板坯 订单 1 2 3 4 5 6 7 8 9 10 1290130013651430145015801580163017801800 1 12（3） 2 16 21（3） 3 7 24（8） 4 20（2） 5 8 2（5） 6 8（4） 7 20 24（2） 8 4 16（10） 9 20（5） 10 8 24（6） 图2 区间值板坯设计 MNOS 算法结果 Fig．2 Results of MNOS algorithm of interval value slab designing 针对由 MNOS 算法产生的有盈余的组合坯 （图2中第3、5、8、10列）应用 MTSW 算法实现盈 余量的最优计算过程如图3所示（图3中第一行 的数字表示板坯号各个矩形阴影中数字表示订单 ·1182· 北 京 科 技 大 学 学 报 第30卷
第10期 席阳等：针对固定重量板坯的板坯设计优化算法 ,1183 号和分配重量，空白表示盈余量) 宽度和重量的需求都为区间值的情况，建立了固定 3 -5 人8 -10 -3 -5 -8 -10 重量板坯的板坯设计模型；利用问题的特殊性质，提 41 41 6 出了板坯相容集合的概念，以此为基础，提出了能 12t 12t 够在板坯数量最小化的前提下，确保总盈余量最小 26 10 241 24 24 化的最优算法，对所提出的算法给出了最优性的理 6 论证明，以及算法应用的实例 12t 参考文献 [1]Balakrishnan A.Geunes J.Production planning with flexible 图3实例的MTSW算法计算过程及结果 product specifications:an application to specialty steel manufac- Fig.3 Results and process of MTSW algorithm in the example turing.Oper Res.2003.51(1):94 为了说明利用区间值需求的效果，将表1中订 [2]Zhou S C.Ding J H.Chen C.Application of the"massive cus- 单区间需求的平均值作为订单的定值需求（表中的 tomization"production mode in iron and steel enterprises.Eng Sci,2006,8(3):1 最后两列数据)，计算出其最优解的各项指标.这些 (周世春，丁建华，陈超“大规模定制“生产模式在钢铁企业的 指标与图2中利用区间值需求得到的解所对应的各 应用实践.中国工程科学，2006,8(3)：1) 项指标的对比结果如表2所示.从对比结果可以看 [3]Frisch A M.Miguel I,Walsh T.Modelling a steel mill slab de- 出，区间值与定值策略在订单完成总重量上基本一 sign problem//Proceedings of the ICAI1 Workshop on Mod- 致，但是在板坯总数和板坯总盈余这两个主要指标 elling and Solving Problems with Constraints.Christian Bessiere,2001:39 上，区间值策略有着明显的优势 [4]Frisch A M.Miguel I.Walsh T.Symmetry and Implied Con- 表2区间值与定值板坯设计策略结果对比 straints in the Steel Mill Slab Design Problem//Proceedings of the Table 2 Comparison of the fixed value model and the interval value CP01 Workshop on Modelling and Problem Formulation. model Christian Bessiere,2001:8 [5]Brahim H.Zeynep K.lan M.et al.Hybrid modelling for robust 板坯 板坯总 订单完成 盈余 策略 总数 盈余 总重量h 率/% solving-Ann Oper Res.2004,130(1/4):19 [6]Denton B.Gupta D.Jawahir K.Managing increasing product va 区间值 58 12 1612 0.74 riety at integrated steel mills.Interfaces.2003.33(2):41 定值 63 133 1631 8.15 [7]Milind D.Jayant K.Ho S L.et al.The slab-design problem in the steel industry.Interfaces.2004.34(3):215 [8]Zhang Y J.Xi Y.Li T K.Model and algorithm for slab design 结论 4 with interval value attributes.Foundry Technol,2008.29(1): 34 固定重量板坯的板坯设计是钢铁生产大规模定 (张英杰，席阳，李铁克，考虑属性区域值的板坯设计模型与算 制中出现的新问题，通过限制板坯重量的变化有利 法.铸造技术，2008,29(1)：34) 于实现推迟定制，达到在满足客户多样化需求的同 [9]Kangbok L.Soo Y C.Hong Y S.Continuous slab caster schedul- 时提高生产效率的目的，本文针对客户订单对板坯 ing and interval graphs.Prod Plann Control.2004.15(5):495
号和分配重量空白表示盈余量）． 图3 实例的 MTSW 算法计算过程及结果 Fig．3 Results and process of MTSW algorithm in the example 为了说明利用区间值需求的效果将表1中订 单区间需求的平均值作为订单的定值需求（表中的 最后两列数据）计算出其最优解的各项指标．这些 指标与图2中利用区间值需求得到的解所对应的各 项指标的对比结果如表2所示．从对比结果可以看 出区间值与定值策略在订单完成总重量上基本一 致但是在板坯总数和板坯总盈余这两个主要指标 上区间值策略有着明显的优势． 表2 区间值与定值板坯设计策略结果对比 Table2 Comparison of the fixed value model and the interval value model 策略 板坯 总数 板坯总 盈余／t 订单完成 总重量／t 盈余 率／％ 区间值 58 12 1612 0∙74 定值 63 133 1631 8∙15 4 结论 固定重量板坯的板坯设计是钢铁生产大规模定 制中出现的新问题通过限制板坯重量的变化有利 于实现推迟定制达到在满足客户多样化需求的同 时提高生产效率的目的．本文针对客户订单对板坯 宽度和重量的需求都为区间值的情况建立了固定 重量板坯的板坯设计模型；利用问题的特殊性质提 出了板坯相容集合的概念．以此为基础提出了能 够在板坯数量最小化的前提下确保总盈余量最小 化的最优算法．对所提出的算法给出了最优性的理 论证明以及算法应用的实例． 参 考 文 献 ［1］ Balakrishnan AGeunes J．Production planning with flexible product specifications：an application to specialty steel manufacturing．Oper Res200351（1）：94 ［2］ Zhou S CDing J HChen C．Application of the “massive customization” production mode in iron and steel enterprises．Eng Sci20068（3）：1 （周世春丁建华陈超．“大规模定制”生产模式在钢铁企业的 应用实践．中国工程科学20068（3）：1） ［3］ Frisch A MMiguel IWalsh T．Modelling a steel mill slab design problem∥ Proceedings of the IJCAI-01 Workshop on Modelling and Solving Problems with Constraints． Christian Bessiere2001：39 ［4］ Frisch A MMiguel IWalsh T．Symmetry and Implied Constraints in the Steel Mill Slab Design Problem∥ Proceedings of the CP-01 Workshop on Modelling and Problem Formulation． Christian Bessiere2001：8 ［5］ Brahim HZeynep KIan Met al．Hybrid modelling for robust solving．A nn Oper Res2004130（1／4）：19 ［6］ Denton BGupta DJawahir K．Managing increasing product variety at integrated steel mills．Interf aces200333（2）：41 ［7］ Milind DJayant KHo S Let al．The slab-design problem in the steel industry．Interf aces200434（3）：215 ［8］ Zhang Y JXi YLi T K．Model and algorithm for slab design with interval value attributes．Foundry Technol200829（1）： 34 （张英杰席阳李铁克．考虑属性区域值的板坯设计模型与算 法．铸造技术200829（1）：34） ［9］ Kangbok LSoo Y CHong Y S．Continuous slab caster scheduling and interval graphs．Prod Plann Control200415（5）：495 第10期 席 阳等： 针对固定重量板坯的板坯设计优化算法 ·1183·