·642· 北京科技大学学报 第33卷 节，因其具有重要的应用价值而受到研究者的关注 与调度的优化管理 目前，该领域的研究文献主要集中在以下几个方面. 本文考虑的板坯设计问题来自于某国有大型钢 (1)针对客户订单的规格需求为固定值的情 铁企业生产管理的实际需求，其前提条件如下： 况，Fish等园分析整理了问题的背景、特点和约束 (1)因连铸机结晶器的限制，板坯的宽度为一 条件；Hnich等回建立了问题的整数规划模型和约 定范围内的确定值： 束规划模型：Gargani等基于逻辑和全局约束，设 (2)为了降低生产组织的复杂性，板坯为定尺 计了将特殊的变量和值选择策略嵌入到大规模领域 规格，即所有板坯的重量相同： 搜索中的求解算法；Van Hentenryck等对文献4] (3)客户订单要求的产品规格与板坯规格间的 中的方法进行了改进和拓展. 对应已经确定，能够被分配到同块板坯的订单必有 (2)针对客户订单的规格需求为区间值的情 相同的板坯宽度需求，在这种情况下可以将板坯设 况，Dawande等针对重量的需求为区间值的问题， 计问题分解为多个板坯宽度相同的相互独立的子 提出了启发式算法：席阳等0在板坯大小可以任意 问题； 切割的前提下，针对客户订单对板坯宽度和重量的 (4)板坯和订单之间可以是多对多的关系，即 需求都为区间值的问题，提出了以最小化板坯数量 一个订单可以被分配到多块板坯，一块板坯也可以 和盈余重量为目标的多项式时间最优算法 包含多个订单的分配重量； (3)针对连铸机生产能力为瓶颈的情况， (5)订单在板坯中有最小分配重量限制： Denton等团研究了以最小化板坯规格数量为目标的 (6)经过前期的预处理，能够保证给定的问题 板坯设计问题；Vonderembse等图与Dash等分别 有可行解. 研究了连铸机只生产两到三种规格的母板坯，在轧 上述板坯设计问题可以抽象为订单的重量为固 制阶段再将母板坯分割成订单所需规格产品的母板 定值，板坯的规格（宽度、重量）相同，订单有最小分 坯设计问题. 配重量限制，以最小化板坯数量为目标的组合优化 近年来，随着市场客户的定制化要求越来越高， 问题.此问题可由一个三元组P=W,D,C)所表示 钢铁企业中高附加价值产品所占的比重越来越大， 的约束满足问题o来描述.V为变量集，V={V, 为了满足对交货产品单位重量约束、热轧后续的酸 V2,…,Vn};D为定义域集，D={D,D2,…,Dn},其 洗镀锌和冷轧等工艺约束要求，在将订单分配到板 中D:为V:的值域；C为约束关系集，C={C,C2, 坯的过程中，常常会有最小重量限制.这些限制破 …,Cm}. 坏了把订单分配到板坯的过程中重量赋值的连续 1.2符号定义 性，改变了问题的复杂性，从而产生了一类新的问 为了便于描述，模型中用到的符号定义如下. 题.其中，客户订单的重量和规格需求都为固定值， 1.2.1集合和索引 板坯的规格相同，具有最小分配重量限制的板坯设 一订单序号； 计问题是最为基础的问题.本文以该问题为对象， 一板坯序号： 建立其约束满足模型，分析问题的复杂性，提出基于 0一订单集合，0={1,2，…，i,…,n}; 问题特殊性质的求解策略和算法，旨在为板坯设计 S一板坯集合，S={1,2,…j,…,m}. 研究提供问题复杂性分析基础和有效的求解框架. 1.2.2参数 g:一订单i的重量； 1问题分析和约束满足模型 δ：一订单i的最小分配限制重量： 1.1问题描述 W一板坯的重量. 钢铁企业的热轧板生产包括炼钢、连铸和热轧 1.2.3变量 三个主要工艺环节，在其生产组织过程中，板坯是衔 x,一订单i分配到板坯j的重量： 接这些环节的物流单元，也是将客户需求和工艺要 y,0-1变量，值为1表示将订单i的重量分 求统一起来的关键所在.在面向订单的生产模式 配到板坯，值为0表示未将订单i的重量分配到板 中，一块板坯中可以包括多个订单，一个订单也可以 坯 被分配到多块板坯中加工生产.通常板坯设计的目 1.3约束满足模型 标是用尽可能少的板坯数给定的客户订单，从而达 基于上述符号，若将变量xy,和m映射为变 到客户需求余材的最小化，同时也有利于生产计划 量集合V:x的值域O,W],y:的值域{0,1}和m的北 京 科 技 大 学 学 报 第 33 卷 节，因其具有重要的应用价值而受到研究者的关注． 目前，该领域的研究文献主要集中在以下几个方面． ( 1) 针对客户订单的规格需求为固定值的情 况，Frisch 等［2］分析整理了问题的背景、特点和约束 条件; Hnich 等［3］建立了问题的整数规划模型和约 束规划模型; Gargani 等［4］基于逻辑和全局约束，设 计了将特殊的变量和值选择策略嵌入到大规模领域 搜索中的求解算法; Van Hentenryck 等［5］对文献［4］ 中的方法进行了改进和拓展． ( 2) 针对客户订单的规格需求为区间值的情 况，Dawande 等［6］针对重量的需求为区间值的问题， 提出了启发式算法; 席阳等［1］在板坯大小可以任意 切割的前提下，针对客户订单对板坯宽度和重量的 需求都为区间值的问题，提出了以最小化板坯数量 和盈余重量为目标的多项式时间最优算法． ( 3) 针对连铸机生产能力为瓶颈的情况， Denton等［7］研究了以最小化板坯规格数量为目标的 板坯设计问题; Vonderembse 等［8］与 Dash 等［9］分别 研究了连铸机只生产两到三种规格的母板坯，在轧 制阶段再将母板坯分割成订单所需规格产品的母板 坯设计问题． 近年来，随着市场客户的定制化要求越来越高， 钢铁企业中高附加价值产品所占的比重越来越大， 为了满足对交货产品单位重量约束、热轧后续的酸 洗镀锌和冷轧等工艺约束要求，在将订单分配到板 坯的过程中，常常会有最小重量限制． 这些限制破 坏了把订单分配到板坯的过程中重量赋值的连续 性，改变了问题的复杂性，从而产生了一类新的问 题． 其中，客户订单的重量和规格需求都为固定值， 板坯的规格相同，具有最小分配重量限制的板坯设 计问题是最为基础的问题． 本文以该问题为对象， 建立其约束满足模型，分析问题的复杂性，提出基于 问题特殊性质的求解策略和算法，旨在为板坯设计 研究提供问题复杂性分析基础和有效的求解框架． 1 问题分析和约束满足模型 1. 1 问题描述 钢铁企业的热轧板生产包括炼钢、连铸和热轧 三个主要工艺环节，在其生产组织过程中，板坯是衔 接这些环节的物流单元，也是将客户需求和工艺要 求统一起来的关键所在． 在面向订单的生产模式 中，一块板坯中可以包括多个订单，一个订单也可以 被分配到多块板坯中加工生产． 通常板坯设计的目 标是用尽可能少的板坯数给定的客户订单，从而达 到客户需求余材的最小化，同时也有利于生产计划 与调度的优化管理． 本文考虑的板坯设计问题来自于某国有大型钢 铁企业生产管理的实际需求，其前提条件如下: ( 1) 因连铸机结晶器的限制，板坯的宽度为一 定范围内的确定值; ( 2) 为了降低生产组织的复杂性，板坯为定尺 规格，即所有板坯的重量相同; ( 3) 客户订单要求的产品规格与板坯规格间的 对应已经确定，能够被分配到同块板坯的订单必有 相同的板坯宽度需求，在这种情况下可以将板坯设 计问题分解为多个板坯宽度相同的相互独立的子 问题; ( 4) 板坯和订单之间可以是多对多的关系，即 一个订单可以被分配到多块板坯，一块板坯也可以 包含多个订单的分配重量; ( 5) 订单在板坯中有最小分配重量限制; ( 6) 经过前期的预处理，能够保证给定的问题 有可行解． 上述板坯设计问题可以抽象为订单的重量为固 定值，板坯的规格( 宽度、重量) 相同，订单有最小分 配重量限制，以最小化板坯数量为目标的组合优化 问题． 此问题可由一个三元组 P =〈V，D，C〉所表示 的约束满足问题［10］来描述． V 为变量集，V = { V1， V2，…，Vn } ; D 为定义域集，D = { D1，D2，…，Dn } ，其 中 Di 为 Vi 的值域; C 为约束关系集，C = { C1，C2， …，Cm } ． 1. 2 符号定义 为了便于描述，模型中用到的符号定义如下． 1. 2. 1 集合和索引 i—订单序号; j—板坯序号; O—订单集合，O = { 1，2，…，i，…，n} ; S—板坯集合，S = { 1，2，…，j，…，m} ． 1. 2. 2 参数 gi—订单 i 的重量; δi—订单 i 的最小分配限制重量; W—板坯的重量． 1. 2. 3 变量 xij —订单 i 分配到板坯 j 的重量; yij —0 － 1 变量，值为 1 表示将订单 i 的重量分 配到板坯 j，值为 0 表示未将订单 i 的重量分配到板 坯 j． 1. 3 约束满足模型 基于上述符号，若将变量 xij 、yij和 m 映射为变 量集合 V; xij的值域［0，W］，yij的值域{ 0，1} 和 m 的 ·642·