柏亮等：基于变邻域搜索的热轧圆钢批量调度多目标优化方法 ·113 罚，而且访问时必须遵守一定的规则，否则也将产生跳 $-c:+0(1-xm）≥0，ij=1,2,…,n, 跃惩罚，目标是获得总成本最小的旅行线路 k=1,2,…,m (9) 为了便于描述，符号及模型表述如下 (s:-s）x0≤0，ij=1,2,…,n,k=1,2,…,m, (1)符号定义. (10) i为轧制单元序号，【为轧制单元序号集合，I= (c-c）xt≤0，ij=1,2,…,n,k=1,2,…,m, {1,2,,n},其中n为轧制单元总数，i∈： (11) k为轧制规格序号，K为轧制规格序号集合，K= lg:-8lxm≤Gsij=1,2,…,n,k=1,2,…,m, {1,2,…,m},其中m为轧制规格总数，k∈K: (12) T:g:和P:分别为轧制单元i的轧制规格、钢种和 s≥0，c≥0，i=1,2,…,n, (13) 轧制时长，其中r∈K,g:和P:均已知； d:为轧制单元i所要求的最晚交货期，可根据其 x+x4=1,i时j=1,2,…,n,i<j,k=1,2,…,m, (14) 所包含钢坯集合的最晚交货期计算得出： s:和c:分别为轧制单元i在连轧机上的开工时间 xm∈{0,1}，i时j=1,2,…,n,i≠j,k=1,2,…,m 和完工时间，则c:=s:+P: (15) ‘u为轧制规格从k切换到k时的设备调整时间， 其中，目标函数(1)表示最小化轧制规格变化引 t=L1a+L,b-+3,其中aw和bw-分别为当轧制规格 起的设备调整时间：目标函数(2)表示最小化轧制单 从k切换到k时的拆卸轧机个数和安装轧机个数，， 元的拖期生产惩罚值：目标函数(3)表示最小化相邻 和2分别为拆卸轧机和安装轧机的单位时间，3为试 轧制单元间钢种跳跃产生的惩罚值：约束(4)表示轧 轧时间； 制单元i最多只能被安排到一个轧制规格内：约束(5) 入为轧制单元拖期生产时的单位惩罚值： 表示轧制单元与轧制规格之间的对应关系：约束(6) 9为在轧制规格k内从轧制单元i到轧制单元j 表示轧制单元i后有且仅有一个轧制单元：约束(7)表 的钢种跳跃惩罚，其中 示轧制单元j前有且仅有一个轧制单元：约束(8)表示 ∫正数，若8：≠g 轧制单元在加工时不允许中断：约束(9)表示前一个 40, 否则： 轧制单元加工完成之后下一个轧制单元才能开始加 G为相邻轧制单元之间钢种跳跃惩罚的上限； 工：约束(10)和约束(11)表示轧制单元间的先后顺序 U为足够大的正整数 关系：约束(12)表示相邻轧制单元间钢种跳跃存在上 (2)变量定义. 限：约束(13)至(15)表示决策变量的取值约束. ,1,若在轧制规格k内轧制单元i在 2求解算法 连轧机上先于轧制单元矿生产， 0, 否则； 由于热轧圆钢的批量调度问题可以归结为扩展型 a=,若轧制规格由k切换为k5， 的非对称旅行商问题，具有NP难的特性，且是一类具 否则： 有多目标、多变量和多约束的组合优化问题，用精确算 1, 轧制单元属于轧制规格k, 法在可行时间内难以求解，智能优化算法是求解NP- a={0,否则 Hard问题的强有力工具.变邻域搜索(variable neigh- (3)数学模型. borhood search,VNS)算法z-l是一种基于邻域搜索 (1) 的智能优化算法，适用于求解组合优化问题，其基本思 min听i= 之y陆-， 想是在搜索过程中系统地改变邻域结构集来拓展搜索 wial. ,max(0,c;-d,), (2) 范围，以达到局部最优解不断地向全局最优解收敛的 目的.根据热轧圆钢批量调度问题的非对称旅行商特 财=含含含 xn (3) 征，针对热轧阶段是连续性很强的批量生产过程，且除 设备检修和设备调试之外，一般不允许出现机器空闲 &ka=l,i=1,2,,n, (4) 的要求.本文对三个优化目标采取串行处理策略，依 lr-klzu=0,i=1,2,…,n,k=1,2,…,m, (5) 据其在管理中的重要程度依次进行优化，即首先计算 品=i=12=12m, (6) 轧制单元的最晚交货期并按照轧制规格数对轧制单元 集合进行分组，然后利用约束满足技术获得一个初始 g=小=12…nk=12…m (7) 可行解，再用变邻域搜索算法优化设备调整时间，其中 C=S+P,i=1,2,…,n, (8) 在构造邻域结构和局部搜索之后采用两层优化的策柏 亮等: 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 罚，而且访问时必须遵守一定的规则，否则也将产生跳 跃惩罚，目标是获得总成本最小的旅行线路． 为了便于描述，符号及模型表述如下． ( 1) 符号定义． i 为轧制单元序号，I 为轧制单元序号集合，I = { 1，2，…，n} ，其中 n 为轧制单元总数，i∈I; k 为轧制规格序号，K 为轧制规格序号集合，K = { 1，2，…，m} ，其中 m 为轧制规格总数，k∈K; ri、gi 和 pi 分别为轧制单元 i 的轧制规格、钢种和 轧制时长，其中 ri∈K，gi 和 pi 均已知; di 为轧制单元 i 所要求的最晚交货期，可根据其 所包含钢坯集合的最晚交货期计算得出; si 和 ci 分别为轧制单元 i 在连轧机上的开工时间 和完工时间，则 ci = si + pi ; tkk'为轧制规格从 k 切换到 k'时的设备调整时间， tkk' = t1 akk' + t2 bkk' + t3，其中 akk'和 bkk'分别为当轧制规格 从 k 切换到 k'时的拆卸轧机个数和安装轧机个数，t1 和 t2 分别为拆卸轧机和安装轧机的单位时间，t3 为试 轧时间; λ 为轧制单元拖期生产时的单位惩罚值; qijk为在轧制规格 k 内从轧制单元 i 到轧制单元 j 的钢种跳跃惩罚，其中 qijk = 正数， 若 gi≠gj ， {0， 否则; Gmax为相邻轧制单元之间钢种跳跃惩罚的上限; U 为足够大的正整数． ( 2) 变量定义． xijk = 1， 若在轧制规格 k 内轧制单元 i 在 连轧机上先于轧制单元 j 生产， 0， 否则 { ; ykk' = 1， 若轧制规格由 k 切换为 k'， {0， 否则; zik = 1， 轧制单元 i 属于轧制规格 k， {0， 否则． ( 3) 数学模型． minf1 = ∑ m k = 1 ∑ m k' = 1 ∑ n i = 1 zik ykk' tkk'， ( 1) minf2 = λ ∑ n i = 1 max ( 0，ci － di ) ， ( 2) minf3 = ∑ n i = 1 ∑ n j = 1 ∑ m k = 1 xijk qijk ． ( 3) s． t． ∑ m k = 1 zik = 1，i = 1，2，…，n， ( 4) | ri － k | zik = 0，i = 1，2，…，n，k = 1，2，…，m， ( 5) j∈ ∑I\{ i} xijk = zik，i = 1，2，…，n，k = 1，2，…，m， ( 6) i∈ ∑I\{ j} xijk = zjk，j = 1，2，…，n，k = 1，2，…，m， ( 7) ci = si + pi，i = 1，2，…，n， ( 8) sj － ci + U( 1 － xijk ) ≥0，i，j = 1，2，…，n， k = 1，2，…，m， ( 9) ( si － sj ) xijk≤0，i，j = 1，2，…，n，k = 1，2，…，m， ( 10) ( ci － cj ) xijk≤0，i，j = 1，2，…，n，k = 1，2，…，m， ( 11) | gi － gj | xijk≤Gmax，i，j = 1，2，…，n，k = 1，2，…，m， ( 12) si≥0，ci≥0，i = 1，2，…，n， ( 13) xijk + xjik = 1，i，j = 1，2，…，n，i ＜ j，k = 1，2，…，m， ( 14) xijk∈{ 0，1} ，i，j = 1，2，…，n，i≠j，k = 1，2，…，m． ( 15) 其中，目标函数( 1) 表示最小化轧制规格变化引 起的设备调整时间; 目标函数( 2) 表示最小化轧制单 元的拖期生产惩罚值; 目标函数( 3) 表示最小化相邻 轧制单元间钢种跳跃产生的惩罚值; 约束( 4) 表示轧 制单元 i 最多只能被安排到一个轧制规格内; 约束( 5) 表示轧制单元与轧制规格之间的对应关系; 约束( 6) 表示轧制单元 i 后有且仅有一个轧制单元; 约束( 7) 表 示轧制单元 j 前有且仅有一个轧制单元; 约束( 8) 表示 轧制单元在加工时不允许中断; 约束( 9) 表示前一个 轧制单元加工完成之后下一个轧制单元才能开始加 工; 约束( 10) 和约束( 11) 表示轧制单元间的先后顺序 关系; 约束( 12) 表示相邻轧制单元间钢种跳跃存在上 限; 约束( 13) 至( 15) 表示决策变量的取值约束． 2 求解算法 由于热轧圆钢的批量调度问题可以归结为扩展型 的非对称旅行商问题，具有 NP 难的特性，且是一类具 有多目标、多变量和多约束的组合优化问题，用精确算 法在可行时间内难以求解，智能优化算法是求解 NP-- Hard 问题的强有力工具． 变邻域搜索( variable neigh￾borhood search，VNS) 算法［12 － 13］是一种基于邻域搜索 的智能优化算法，适用于求解组合优化问题，其基本思 想是在搜索过程中系统地改变邻域结构集来拓展搜索 范围，以达到局部最优解不断地向全局最优解收敛的 目的． 根据热轧圆钢批量调度问题的非对称旅行商特 征，针对热轧阶段是连续性很强的批量生产过程，且除 设备检修和设备调试之外，一般不允许出现机器空闲 的要求． 本文对三个优化目标采取串行处理策略，依 据其在管理中的重要程度依次进行优化，即首先计算 轧制单元的最晚交货期并按照轧制规格数对轧制单元 集合进行分组，然后利用约束满足技术获得一个初始 可行解，再用变邻域搜索算法优化设备调整时间，其中 在构造邻域结构和局部搜索之后采用两层优化的策 · 311 ·