114 工程科学学报，第37卷，第1期 略，即每次最优设备调整时间发生变化时，采用最早交 Sep2变量选择.对于当前轧制规格k,按最晚 货期优先(earliest due date first,EDD)和钢种排序规 交货期非减的顺序对轧制单元集合进行排序，选择交 则来优化拖期生产惩罚和钢种跳跃惩罚，最终得到该 货期最早的轧制单元作为种子轧制单元：在轧制规格 问题一个合理有效的解 k内依序选择变量，执行Step3~Step4,若轧制规格k 2.1轧制单元预处理 内的变量均已赋值，则进入下一个轧制规格，直到所有 由于每个轧制单元内钢坯集合的最晚交货期各不 变量均被赋值，则转Step5. 相同，因此为了计算轧制单元的最晚交货期，需要对轧 Step3值选择.针对已选择的变量i,当轧制规格 制单元内的钢坯集合进行预处理.此外，针对设备调 未发生切换时，则jeI,i≠j,根据式min{lg:-gl} 整时间是主要优化目标，且轧制规格相同的轧制单元 选择与变量i间钢种跳跃惩罚最小的变量j作为值选 间不需要设备调整的实际情况，先对轧制单元集合按 择的对象：当轧规格发生切换时，则Hk∈K,k≠k, 轧制规格进行分组处理.令【为轧制单元内的钢坯 根据式t址=1a+l2b+计算设备调整时间，选择 序号，V,为轧制单元i所包含的钢坯集合，其中V,= 设备调整时间最短的轧制规格k内最晚交货期最早的 {1,2,…,n,},n:为轧制单元i内的钢坯总数，l∈VPi 变量作为值选择的对象 为轧制单元i内钢坯1的轧制时长，d为轧制单元i内 Slep4约束传播.在变量的值选择之后，根据式 钢坯1的最晚交货期.具体步骤如下： (8)按相邻轧制单元间钢种跳跃惩罚上限，对变量的 Stepl对每个轧制单元i内的钢坯集合V,初始 值域进行基于能力约束传播的一致性检查，从中剔除 化最晚交货期，并获得最晚交货期最早的钢坯L 不符合条件的轧制单元 Step5算法结束.输出轧制单元序列作为热轧圆 Sp2根据式d=心+及片计第轧制单元：的 钢批量调度问题的初始解，算法终止 最晚交货期，其中为轧制单元内钢坯l,的最晚交 2.3构造邻域结构 货期. 在变邻域搜索算法中，邻域结构的构造过程是算 Step3按轧制规格总数将轧制单元集合I划分为 法设计的核心部分之一，其主要目的是扩展当前解的 m组(m<n),即共享同一套孔型系统的轧制单元划分 搜索空间，减小算法陷入局部最优解的可能性，使得算 到同一分组内：记I为轧制规格k所对应的轧制单元 法能够求得较好的解，尽量保证算法的全局性.在构 分组，即Hi,j∈I,有r:=r:在分组I.内按EDD准则 造邻域结构时，首先从当前解x的邻域结构集中选取 对轧制单元进行处理 一个邻域结构N,然后根据N的定义对x做相应的 2.2构造初始解 改变生产新的解x。通常，解的全局性好则找到最优 由于初始解的优劣直接影响变邻域搜索算法的性 解的可能性高，但同时所需的求解时间也较长 能，而良好的初始解可以保证变邻域搜索算法能在较 结合热轧圆钢批量调度的问题特征，设备调整时 短时间内获得全局最优解或近优解，因此这里采用约 间仅与轧制规格序列相关，而其是一条起点和终点不 束满足算法得到一个较好的初始可行解.对于本文研 确定的开环路径.因此，本文采用将插入算子(insert) 究的批量调度问题，若将各轧制单元映射为变量V,变 和交换算子(swap)相结合的方式来构造邻域结构集 量取值的可选范围映射为变量的值域D,交货期约束 合.具体如下. 和钢种集中约束映射为约束集合C,则热轧圆钢批量 (l)Insert算子.在当前解中随机选择节点A,将 调度问题就转化为约束满足问题(Constraint satisfac- 其插入其他位置形成新的解，所有可能形成的新解构 tion problem,CSP)4-O=(V,D,C).对于这类具有 成了当前解关于节点A的插入式邻域： 复杂约束的约束满足问题，可以利用变量之间的约束 (2)Swap算子.在当前解中随机选择节点A,再 关系，通过变量选择、值选择和约束传播等方法，从变 另选节点B,将这两点交换位置后形成新的解，所有可 量的值域中预先或动态地消除非法解、修剪搜索空间 能形成的新解构成当前解关于节点A的交换式邻域. 和减少组合爆炸，进而获得高质量的初始可行解 在每次构造邻域结构时，变邻域搜索算法每次将 因此，结合以上问题特征，本文利用约束满足中的 交替选取一种算子来生成邻域结构.通过以上两种算 变量选择、值选择和约束传播等技术来进行轧制单元 子的交替使用，可以确保当前解的大部分特征会被保 的分组和排序.具体步骤如下 留下来，在一定程度上加快了算法的收敛速度 Stepl值域约简.为了修剪搜索空间，消除无效 2.4局部搜索 搜索，提高搜索效率，去除值域中的非可行解，根据轧 局部搜索是变邻域搜索算法的另一个核心部分， 制单元的分组情况，将每个轧制单元i的值域约减为 即对每次生成的邻域结构分别进行局部搜索，求得各 D:=Ujli≠j,i,jeI}. 自邻域内的局部最优解.局部搜索是整个变邻域搜索工程科学学报，第 37 卷，第 1 期 略，即每次最优设备调整时间发生变化时，采用最早交 货期优先( earliest due date first，EDD) 和钢种排序规 则来优化拖期生产惩罚和钢种跳跃惩罚，最终得到该 问题一个合理有效的解． 2. 1 轧制单元预处理 由于每个轧制单元内钢坯集合的最晚交货期各不 相同，因此为了计算轧制单元的最晚交货期，需要对轧 制单元内的钢坯集合进行预处理． 此外，针对设备调 整时间是主要优化目标，且轧制规格相同的轧制单元 间不需要设备调整的实际情况，先对轧制单元集合按 轧制规格进行分组处理． 令 l 为轧制单元 i 内的钢坯 序号，Vi 为轧制单元 i 所包含的钢坯集合，其中 Vi = { 1，2，…，ni} ，ni 为轧制单元 i 内的钢坯总数，l∈Vi ; pi l 为轧制单元 i 内钢坯 l 的轧制时长，di l 为轧制单元 i 内 钢坯 l 的最晚交货期． 具体步骤如下: Step1 对每个轧制单元 i 内的钢坯集合 Vi，初始 化最晚交货期，并获得最晚交货期最早的钢坯 l1 ． Step2 根据式 di = di 1 + ∑ ni l = 2 pi l 计算轧制单元 i 的 最晚交货期，其中 di 1 为轧制单元 i 内钢坯 l1 的最晚交 货期． Step3 按轧制规格总数将轧制单元集合 I 划分为 m 组( m ＜ n) ，即共享同一套孔型系统的轧制单元划分 到同一分组内; 记 Ik 为轧制规格 k 所对应的轧制单元 分组，即i，j∈Ik，有 ri = rj ; 在分组 Ik 内按 EDD 准则 对轧制单元进行处理． 2. 2 构造初始解 由于初始解的优劣直接影响变邻域搜索算法的性 能，而良好的初始解可以保证变邻域搜索算法能在较 短时间内获得全局最优解或近优解，因此这里采用约 束满足算法得到一个较好的初始可行解． 对于本文研 究的批量调度问题，若将各轧制单元映射为变量 V，变 量取值的可选范围映射为变量的值域 D，交货期约束 和钢种集中约束映射为约束集合 C，则热轧圆钢批量 调度问题就转化为约束满足问题( Constraint satisfac￾tion problem，CSP) ［14 － 15］Θ = ( V，D，C) ． 对于这类具有 复杂约束的约束满足问题，可以利用变量之间的约束 关系，通过变量选择、值选择和约束传播等方法，从变 量的值域中预先或动态地消除非法解、修剪搜索空间 和减少组合爆炸，进而获得高质量的初始可行解． 因此，结合以上问题特征，本文利用约束满足中的 变量选择、值选择和约束传播等技术来进行轧制单元 的分组和排序． 具体步骤如下． Step1 值域约简． 为了修剪搜索空间，消除无效 搜索，提高搜索效率，去除值域中的非可行解，根据轧 制单元的分组情况，将每个轧制单元 i 的值域约减为 Di = { j | i≠j，i，j∈Ik } ． Step2 变量选择． 对于当前轧制规格 k，按最晚 交货期非减的顺序对轧制单元集合进行排序，选择交 货期最早的轧制单元作为种子轧制单元; 在轧制规格 k 内依序选择变量，执行 Step3 ～ Step4，若轧制规格 k 内的变量均已赋值，则进入下一个轧制规格，直到所有 变量均被赋值，则转 Step5． Step3 值选择． 针对已选择的变量 i，当轧制规格 未发生切换时，则j∈Ik，i≠j，根据式 min { | gi － gj | } 选择与变量 i 间钢种跳跃惩罚最小的变量 j 作为值选 择的对象; 当轧制规格发生切换时，则k'∈K，k≠k'， 根据式 tkk' = t1 akk' + t2 bkk' + t3 计算设备调整时间，选择 设备调整时间最短的轧制规格 k'内最晚交货期最早的 变量 j 作为值选择的对象． Step4 约束传播． 在变量的值选择之后，根据式 ( 8) 按相邻轧制单元间钢种跳跃惩罚上限，对变量的 值域进行基于能力约束传播的一致性检查，从中剔除 不符合条件的轧制单元． Step5 算法结束． 输出轧制单元序列作为热轧圆 钢批量调度问题的初始解，算法终止． 2. 3 构造邻域结构 在变邻域搜索算法中，邻域结构的构造过程是算 法设计的核心部分之一，其主要目的是扩展当前解的 搜索空间，减小算法陷入局部最优解的可能性，使得算 法能够求得较好的解，尽量保证算法的全局性． 在构 造邻域结构时，首先从当前解 x 的邻域结构集中选取 一个邻域结构 Nk，然后根据 Nk 的定义对 x 做相应的 改变生产新的解 xn ． 通常，解的全局性好则找到最优 解的可能性高，但同时所需的求解时间也较长． 结合热轧圆钢批量调度的问题特征，设备调整时 间仅与轧制规格序列相关，而其是一条起点和终点不 确定的开环路径． 因此，本文采用将插入算子( insert) 和交换算子( swap) 相结合的方式来构造邻域结构集 合． 具体如下． ( 1) Insert 算子． 在当前解中随机选择节点 A，将 其插入其他位置形成新的解，所有可能形成的新解构 成了当前解关于节点 A 的插入式邻域; ( 2) Swap 算子． 在当前解中随机选择节点 A，再 另选节点 B，将这两点交换位置后形成新的解，所有可 能形成的新解构成当前解关于节点 A 的交换式邻域． 在每次构造邻域结构时，变邻域搜索算法每次将 交替选取一种算子来生成邻域结构． 通过以上两种算 子的交替使用，可以确保当前解的大部分特征会被保 留下来，在一定程度上加快了算法的收敛速度． 2. 4 局部搜索 局部搜索是变邻域搜索算法的另一个核心部分， 即对每次生成的邻域结构分别进行局部搜索，求得各 自邻域内的局部最优解． 局部搜索是整个变邻域搜索 · 411 ·