·644· 北京科技大学学报 第33卷 此，本文提出每次选择一个订单一板坯对，并对其进 策略进行订单一板坯对的选择和订单重量分配.基 行订单重量分配的循环求解框架，进而在此框架下 于上述定义1~定义4，可以将基于约束满足技术的 开发求解算法 可分配订单一板坯对的选择以及订单重量分配方法 [循环求解框架] 的要点叙述如下. 1.Initialize 3.2.1最小自由度优先策略 2.While (not terminate-eondition)do 作为针对y:的变量选择方法：参照困难变量优 2.1 select 0;and S 先赋值的思想，并结合板坯设计问题的特点，提出下 2.2 if (not exist S,)then add a new S;for 0 述的最小自由度优先策略. 2.3 assign the weight of 0;to S. 最小自由度优先策略] 2.4 update variable 订单选择规则：计算亚：；除去I亚：|=0的订单 显然在上述求解框架中，算法的可行性和有效 外，选择min{1亚I}的O,;当l亚I=I亚l时，选择 性主要取决于在每次循环中：(1)如何选取订单一板 min{ygy}的0：当y=时，选择min{p:/6, 坯对：(2)对已选取的订单一板坯对，如何将订单重 P/6}的0g. 量分配到板坯.为了对这些问题做进一步的探讨， 板坯选择规则：对O,计算中，j∈乎：除去 给出以下相关定义. I中I=0的板坯外，优先选择1①：I小的S;当 定义1订单i的未分配重量P:是指该订单的 IΦ，I=|ΦI时，优先选择min{cc}的S· 重量g:减去该订单己经分配到板坯中的重量后所 通过上述最小自由度优先策略可确定优先赋值 剩余量：板坯j的盈余量c,是指其重量中没有订单 的变量y,并得到一个可分配订单一板坯对(， 对应的部分 ).这种选择策略具有计算量小，可以避免构造不 定义2订单i能够被分配到板坯j是指满足 可行的部分解的优点. 下面条件：板坯j尚未包含订单i(记为O:S),8≤ 3.2.2最大可行量分配策略 min{p:c},且若c<pP:时必须有2δ，≤P:此时称(i, 作为针对x:的值选择方法：按照最先成功原则 )为可分配订单一板坯对. 赋值，即给变量赋予使得尽可能多的约束成立的值 定义3订单i的自由度|亚：|是指该订单能够 参照最先成功原则并结合板坯设计问题的特点，提 分配的板坯数，其中平：表示订单i能够被分配的板 出下述的最大可行量分配策略.即，对己选取的可 坯集合 分配订单一板坯对(i,),按以下规则处理 定义4板坯j的自由度1ΦI是指能够被分配 到该板坯的订单数，其中中，表示能够被分配到板坯 最大可行量分配策略] j的订单集合. 规则1若P:≤C,则x可=P: 3.2基于约束满足的求解策略 规则2若P:>G和P:-C,≥6，则x=C; 约束满足是求解大规模组合优化问题的一种有 规则3若p:>G和P:-G<6,则x=p:-6 效的智能近似方法，其用一个变量集、变量的值域和 最大可行量分配策略具有以下特点：保证解的 限制变量取值的约束集描述组合优化问题，约 可行性；每个订单一板坯对之间最多只进行一次订 束满足问题的求解是从变量的值域中寻找一组满足 单重量分配：将变量x的赋值的可行域由连续转变为 约束的值赋给变量，主要求解技术包含一致性技术、 离散这些特点为开发高效的近似算法提供了基础 约束传播技术、变量选择和值选择搜索算法@.搜 3.3算法描述 索算法通过不断选择下一个待赋值变量并为该变量 在上述分析的基础上，设O'为待分配订单集 选择一个值来逐步实现问题的求解，该过程称为变 合，S为所需板坯集合，可将本文提出的采用约束满 量选择和值选择.变量的选择顺序和值的选择顺序 足技术最小化板坯数(constraint satisfaction for 直接决定求解效率和寻优性能，通常要根据问题的 minimizing slab quantity,CSMSQ)算法描述如下. 特征构造变量选择和值选择启发式搜索算法：变量 [CSMSQ算法] 选择顺序一般遵循困难变量优先赋值的规则，值选 Step1(初始化) 择顺序遵循将最有希望构成全局解的值优先赋给 输入订单数据和相关参数：0'=0，S=☑，m= 变量 0,Φ=，Ψ：=☑，P:=g:和c=W,Vi,j 本文利用约束满足技术中的变量选择和值选择 Step2（变量选择：选取可分配订单-板坯对)北 京 科 技 大 学 学 报 第 33 卷 此，本文提出每次选择一个订单--板坯对，并对其进 行订单重量分配的循环求解框架，进而在此框架下 开发求解算法． ［循环求解框架］ 1. Initialize 2. While ( not terminate-condition) do 2. 1 select Oi and Sj 2. 2 if ( not exist Sj ) then add a new Sj for Oi 2. 3 assign the weight of Oi to Sj 2. 4 update variable 显然在上述求解框架中，算法的可行性和有效 性主要取决于在每次循环中: ( 1) 如何选取订单--板 坯对; ( 2) 对已选取的订单--板坯对，如何将订单重 量分配到板坯． 为了对这些问题做进一步的探讨， 给出以下相关定义． 定义 1 订单 i 的未分配重量 pi 是指该订单的 重量 gi 减去该订单已经分配到板坯中的重量后所 剩余量; 板坯 j 的盈余量 cj 是指其重量中没有订单 对应的部分． 定义 2 订单 i 能够被分配到板坯 j 是指满足 下面条件: 板坯 j 尚未包含订单 i( 记为 OiSj ) ，δi≤ min{ pi，cj } ，且若 cj ＜ pi 时必须有 2δi≤pi ; 此时称( i， j) 为可分配订单--板坯对． 定义 3 订单 i 的自由度 | Ψi | 是指该订单能够 分配的板坯数，其中 Ψi 表示订单 i 能够被分配的板 坯集合． 定义 4 板坯 j 的自由度 | Φj | 是指能够被分配 到该板坯的订单数，其中 Φj 表示能够被分配到板坯 j 的订单集合． 3. 2 基于约束满足的求解策略 约束满足是求解大规模组合优化问题的一种有 效的智能近似方法，其用一个变量集、变量的值域和 限制变量取值的约束集描述组合优化问题［11］． 约 束满足问题的求解是从变量的值域中寻找一组满足 约束的值赋给变量，主要求解技术包含一致性技术、 约束传播技术、变量选择和值选择搜索算法［10］． 搜 索算法通过不断选择下一个待赋值变量并为该变量 选择一个值来逐步实现问题的求解，该过程称为变 量选择和值选择． 变量的选择顺序和值的选择顺序 直接决定求解效率和寻优性能，通常要根据问题的 特征构造变量选择和值选择启发式搜索算法; 变量 选择顺序一般遵循困难变量优先赋值的规则，值选 择顺序遵循将最有希望构成全局解的值优先赋给 变量． 本文利用约束满足技术中的变量选择和值选择 策略进行订单--板坯对的选择和订单重量分配． 基 于上述定义 1 ～ 定义 4，可以将基于约束满足技术的 可分配订单--板坯对的选择以及订单重量分配方法 的要点叙述如下． 3. 2. 1 最小自由度优先策略 作为针对 yij的变量选择方法: 参照困难变量优 先赋值的思想，并结合板坯设计问题的特点，提出下 述的最小自由度优先策略． ［最小自由度优先策略］ 订单选择规则: 计算 Ψi ; 除去 | Ψi | = 0 的订单 外，选择 min { | Ψi |} 的 Oi* ; 当| Ψi | = | Ψi' | 时，选择 min { yij ，yi'j'} 的 Oi* ; 当 yij = yi'j' 时，选择 min{ pi / δi， pi' / δi'} 的 Oi* ． 板坯选择规则: 对 Oi* ，计算 Φj ，j∈Ψi* ; 除去 | Φj | = 0的 板 坯 外，优 先 选 择 | Φj | 小 的 Sj* ; 当 | Φj | = | Φj' |时，优先选择 min{ cj ，cj'} 的 Sj* ． 通过上述最小自由度优先策略可确定优先赋值 的变量 yij ，并得到一个可分配订单--板 坯 对( i * ， j * ) ． 这种选择策略具有计算量小，可以避免构造不 可行的部分解的优点． 3. 2. 2 最大可行量分配策略 作为针对 xij的值选择方法: 按照最先成功原则 赋值，即给变量赋予使得尽可能多的约束成立的值． 参照最先成功原则并结合板坯设计问题的特点，提 出下述的最大可行量分配策略． 即，对已选取的可 分配订单--板坯对( i，j) ，按以下规则处理． ［最大可行量分配策略］ 规则 1 若 pi≤cj ，则 xij = pi ; 规则 2 若 pi ＞ cj 和 pi － cj≥δi，则 xij = cj ; 规则 3 若 pi ＞ cj 和 pi － cj ＜ δi，则 xij = pi － δi ． 最大可行量分配策略具有以下特点: 保证解的 可行性; 每个订单--板坯对之间最多只进行一次订 单重量分配; 将变量 xij的赋值的可行域由连续转变为 离散． 这些特点为开发高效的近似算法提供了基础． 3. 3 算法描述 在上述分析的基础上，设 O'为待分配订单集 合，S'为所需板坯集合，可将本文提出的采用约束满 足技 术 最 小 化 板 坯 数 ( constraint satisfaction for minimizing slab quantity，CSMSQ) 算法描述如下． ［CSMSQ 算法］ Step 1 ( 初始化) 输入订单数据和相关参数; O' = O，S' = ，m = 0，Φj = ，Ψi = ，pi = gi 和 cj = W，i，j． Step 2 ( 变量选择: 选取可分配订单--板坯对) ·644·