基于变邻域搜索的热轧圆钢批量调度多目标优化方法

工程科学学报，第37卷，第1期：111117,2015年1月 Chinese Journal of Engineering,Vol.37,No.1:111-117,January 2015 DOI:10.13374/j.issn2095-9389.2015.01.017:http://journals.ustb.edu.cn 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 柏 亮12)区，李铁克12》，王柏琳12》，许绍云12)，董广静2) 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 ☒通信作者，E-mail:bailiang908@139.com 摘要针对热轧圆钢的批量调度问题，考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响，建立了以最小化设 备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型，并设计了一种嵌入EDD规则的变邻域搜索算法.算法首 先结合模型的约束特征，采用约束满足技术生成初始解：根据实际生产需求，将最小化设备调整时间作为主要目标，设计变邻 域搜索算法实现目标优化，其中，运用混合算子构造邻域结构和局部搜索，并引入模拟退火接受准则来控制迭代过程中产生 的新解：同时，为了最小化拖期惩罚和钢种跳跃惩罚，在求解过程中嵌入了EDD规则以及钢种排序规则.实验结果表明，模型 和算法是可行且有效的 关键词热轧：调度：变邻域搜索：多目标优化：约束满足问题 分类号F273.1 Variable neighborhood search based multi-objective optimization method for batch scheduling of hot-rolled bars BAI Liang LI Tie-ke,WANG Bai-in XU Shao-yun DONG Guang jing 1)Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron Steel Production (the Ministry of Education),Beijing 100083,China Corresponding author,E-mail:bailiang908@139.com ABSTRACT A batch scheduling problem of hot-rolled bars was discussed according to the influences of process conditions and due date on the continuous production of rolling units.A mathematical model with three objectives to minimize the setup time,tardiness penalty and steel grade bounce penalty was constructed,and a method of the variable neighborhood search algorithm embedding the earliest due date first (EDD)rule was proposed to solve the model.In consideration of constraints in the model,an initial solution was generated by constraint satisfaction technology.Then,to meet the actual production needs,a variable neighborhood search method was designed to minimize the setup time,which is considered as a primary objective.In this algorithm,a hybrid operator is applied in sha- king and local search,and the idea of simulated annealing is introduced to take control of the acceptance of new solutions.Meanwhile, in order to minimize the tardiness penalty and the steel grade bounce penalty,the earliest due date first rule and the steel grade sorting rule are applied.Experiment results show that the model and the algorithm are feasible and effective. KEY WORDS hot rolling:scheduling:variable neighborhood search:multi-objective optimization:constraint satisfaction problems 在整个钢铁生产过程中，热轧不仅是生产成品、直即为了保证产品质量、降低生产成本和提高生产效率， 接创造经济效益的瓶颈工序，而且是衔接炼钢、连铸和 一般以热轧为核心，将具有相同特性的销售订单进行 冷轧的关键工序.热轧阶段是典型的批量生产过程， 合理的归并与拆分，得到在热轧生产过程中连续不允 收稿日期：2013-11-26 基金项目：国家自然科学基金资助项目(71231001)：中央高校基本科研业务费专项资金资助项目(FRF-SD一2011B,FRF-SD-12O12B):教 育部博士学科点专项科研基金资助项目(20100006110006)

工程科学学报，第 37 卷，第 1 期: 111--117，2015 年 1 月 Chinese Journal of Engineering，Vol． 37，No． 1: 111--117，January 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 01． 017; http: / /journals． ustb． edu． cn 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 柏 亮1，2) ，李铁克1，2) ，王柏琳1，2) ，许绍云1，2) ，董广静1，2) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083  通信作者，E-mail: bailiang908@ 139． com 摘 要 针对热轧圆钢的批量调度问题，考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响，建立了以最小化设 备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型，并设计了一种嵌入 EDD 规则的变邻域搜索算法． 算法首 先结合模型的约束特征，采用约束满足技术生成初始解; 根据实际生产需求，将最小化设备调整时间作为主要目标，设计变邻 域搜索算法实现目标优化，其中，运用混合算子构造邻域结构和局部搜索，并引入模拟退火接受准则来控制迭代过程中产生 的新解; 同时，为了最小化拖期惩罚和钢种跳跃惩罚，在求解过程中嵌入了 EDD 规则以及钢种排序规则． 实验结果表明，模型 和算法是可行且有效的． 关键词 热轧; 调度; 变邻域搜索; 多目标优化; 约束满足问题 分类号 F273. 1 Variable neighborhood search based multi-objective optimization method for batch scheduling of hot-rolled bars BAI Liang1，2)  ，LI Tie-ke1，2) ，WANG Bai-lin1，2) ，XU Shao-yun1，2) ，DONG Guang-jing1，2) 1) Donlinks School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Ｒesearch Center of MES Technology for Iron ＆ Steel Production ( the Ministry of Education) ，Beijing 100083，China  Corresponding author，E-mail: bailiang908@ 139． com ABSTＲACT A batch scheduling problem of hot-rolled bars was discussed according to the influences of process conditions and due date on the continuous production of rolling units． A mathematical model with three objectives to minimize the setup time，tardiness penalty and steel grade bounce penalty was constructed，and a method of the variable neighborhood search algorithm embedding the earliest due date first ( EDD) rule was proposed to solve the model． In consideration of constraints in the model，an initial solution was generated by constraint satisfaction technology． Then，to meet the actual production needs，a variable neighborhood search method was designed to minimize the setup time，which is considered as a primary objective． In this algorithm，a hybrid operator is applied in sha￾king and local search，and the idea of simulated annealing is introduced to take control of the acceptance of new solutions． Meanwhile， in order to minimize the tardiness penalty and the steel grade bounce penalty，the earliest due date first rule and the steel grade sorting rule are applied． Experiment results show that the model and the algorithm are feasible and effective． KEY WOＲDS hot rolling; scheduling; variable neighborhood search; multi-objective optimization; constraint satisfaction problems 收稿日期: 2013--11--26 基金项目: 国家自然科学基金资助项目( 71231001) ; 中央高校基本科研业务费专项资金资助项目( FＲF--SD--12--011B，FＲF--SD--12--012B) ; 教 育部博士学科点专项科研基金资助项目( 20100006110006) 在整个钢铁生产过程中，热轧不仅是生产成品、直 接创造经济效益的瓶颈工序，而且是衔接炼钢、连铸和 冷轧的关键工序． 热轧阶段是典型的批量生产过程， 即为了保证产品质量、降低生产成本和提高生产效率， 一般以热轧为核心，将具有相同特性的销售订单进行 合理的归并与拆分，得到在热轧生产过程中连续不允

·112 工程科学学报，第37卷，第1期 许拆分的最小生产批次.因此，研究热轧阶段的批量 (1)轧制不同规格的圆钢需要的轧机数目不同， 调度优化方法，对于提高钢铁企业轧制技术的现代化 即不同规格的圆钢对应的孔型系统不同： 具有重要的理论价值和现实意义. (2)当轧制规格发生变化时，需要进行轧机的安 热轧批量调度问题是一类复杂的组合优化问题， 装与拆卸操作，且需要额外的试轧过程，因此为了保证 直吸引着业者和学者的研究和关注.文献]研究 产品质量、降低生产成本和提高生产效率，一般要确保 了热轧批量调度问题，提出了基于规则的热轧批量调 规格相同的圆钢集中轧制： 度排产启发式算法；文献2]针对板材的热轧批量调 (3)两两轧制规格间的设备调整时间是非对称 度问题，建立了带软时间窗的车辆路径问题模型，设计 的，因而合理的轧制规格序列能有效地提高设备利 了基于约束满足和kopt互换的算法进行求解：文献 用率： B]研究了生产调度中多约束排序问题的求解方法， (4)根据交货期要求，若轧制单元的完工时间晚 并用于求解热轧带钢批量调度问题：文献4]将热轧 于规定的交货时间，将会产生拖期生产成本： 批量调度问题归结为多路径问题，并提出一种基于精 (⑤)相同钢种的轧制单元应尽可能集中生产，以 确算法和启发式算法的混合算法对问题求解：文献 节约产能和保证产品质量 5]从生产成本和产品质量的角度研究了板材的热轧 在编制轧制计划时，计划人员首先根据工艺规范 批量调度问题，并将热装率作为其中一个优化目标：文 对销售订单进行坯料设计和轧制组批，在不违反能力 献6-7]将热轧批量调度问题归结为多目标的奖金 约束的条件下，设计得出轧制单元集合，将其作为热轧 收集车辆路径问题，并分别用基于Pareto最优和基于 阶段的最小批次来组织生产.在轧制组批完成之后， 分解策略的蚁群算法对问题进行求解；文献⑧]针对 需要对轧制单元集合进行生产顺序的排定，使得机器 热轧无缝管的批量调度问题，将问题归结为机器调整 设备总的调整时间最短，这一过程可以归结为与顺序 时间与加工顺序相关的Job-shop问题，分别用分支定 相关的单机批调度问题(single machine batch schedu- 界法和两阶段启发式算法进行求解：文献9]也研究 ling problem with sequence-dependent setup time). 了热轧无缝管的批量调度问题，其中额外考虑了设备 热轧圆钢的轧制特点，本文将轧制单元定义为轧制规 产能、机器检修、前置库存等因素：文献几0]在考虑轧 格和钢种相同，以及交货期相同或相近的钢坯集合，也 机维修约束的基础上，研究了棒线材的热轧批量调度 即可以在一个批次内生产的钢坯序列 问题.以上文献以热轧阶段为背景，从数学模型和算 综上所述，热轧圆钢的批量调度问题可以描述为： 法的角度出发，对不同类型的批量调度问题进行了研 假设有n个待轧制的轧制单元，每个轧制单元的轧制 究，各模型所考虑的目标函数和约束条件均与问题背 规格、钢种、交货期等属性均已知，批量调度问题就是 景有关.目前为止，热轧批量调度的对象主要集中在 对轧制单元集合进行合理有效的排序，使得生产过程 板材、带钢、无缝管、棒线材等产品上，结合热轧圆钢特 中产生的设备调整时间、拖期生产惩罚和钢种跳跃惩 点的批量调度问题的研究成果相对较少 罚最小，其中设备调整时间对于生产成本、生产效率以 本文在已有研究的基础上，针对热轧圆钢的生产 及生产连续性有着重要意义·因此，本文结合实际生 特点，在销售订单组批完成和轧制单元划分完毕的前 产过程中不同指标重要程度的差异性，采用串联方式 提下，建立了以最小化设备调整时间、拖期生产惩罚和 按“设备调整时间→拖期生产惩罚→钢种跳跃惩罚” 钢种跳跃惩罚为优化目标的热轧圆钢批量调度问题模 的重要程度排序，在求解过程中对三个指标进行串行 型，来达到降低生产成本，减少生产延误率和提高客户 寻优 响应度，实现最大化利润的目标.结合问题特征，基于 1.2问题模型 变邻域搜索技术设计了求解算法，并用实际生产数据 热轧圆钢的批量调度问题是一类设备调整时间与 来验证所提出模型和算法的有效性. 加工顺序有关的单机调度问题，即对轧制单元进行排 序，保证在总的设备调整时间最小的前提下，尽可能使 1问题建模 拖期生产费用和钢种跳跃惩罚最小.该问题实质上可 1.1问题描述 以归结为一个扩展型的非对称旅行商问题(asymmetric 连轧机是圆钢在热轧阶段的核心设备，一般由粗 travelling salesman problem,ATSP)u,其中每个轧制 轧机组、中轧机组和精轧机组构成，每类机组由不同数 单元等价于一个城市，任意两个城市之间的距离为两 量的轧机构成，从粗轧到中轧，再到精轧，装有不同类 个轧制单元间的设备调整时间，且呈现非对称特征，则 型轧辊的轧机组合在一起，构成了热轧圆钢轧制的孔 问题描述如下：一个旅行商要访问n个城市（轧制单 型系统.因此，相对于其他钢铁产品，热轧圆钢的轧制 元)，要求每个城市（轧制单元）都被访问一次且仅一 过程有如下特点： 次，尽可能在某个时间之前被访问，否则将产生延误惩

工程科学学报，第 37 卷，第 1 期 许拆分的最小生产批次． 因此，研究热轧阶段的批量 调度优化方法，对于提高钢铁企业轧制技术的现代化 具有重要的理论价值和现实意义． 热轧批量调度问题是一类复杂的组合优化问题， 一直吸引着业者和学者的研究和关注． 文献［1］研究 了热轧批量调度问题，提出了基于规则的热轧批量调 度排产启发式算法; 文献［2］针对板材的热轧批量调 度问题，建立了带软时间窗的车辆路径问题模型，设计 了基于约束满足和 k-opt 互换的算法进行求解; 文献 ［3］研究了生产调度中多约束排序问题的求解方法， 并用于求解热轧带钢批量调度问题; 文献［4］将热轧 批量调度问题归结为多路径问题，并提出一种基于精 确算法和启发式算法的混合算法对问题求解; 文献 ［5］从生产成本和产品质量的角度研究了板材的热轧 批量调度问题，并将热装率作为其中一个优化目标; 文 献［6 － 7］将热轧批量调度问题归结为多目标的奖金 收集车辆路径问题，并分别用基于 Pareto 最优和基于 分解策略的蚁群算法对问题进行求解; 文献［8］针对 热轧无缝管的批量调度问题，将问题归结为机器调整 时间与加工顺序相关的 Job-shop 问题，分别用分支定 界法和两阶段启发式算法进行求解; 文献［9］也研究 了热轧无缝管的批量调度问题，其中额外考虑了设备 产能、机器检修、前置库存等因素; 文献［10］在考虑轧 机维修约束的基础上，研究了棒线材的热轧批量调度 问题． 以上文献以热轧阶段为背景，从数学模型和算 法的角度出发，对不同类型的批量调度问题进行了研 究，各模型所考虑的目标函数和约束条件均与问题背 景有关． 目前为止，热轧批量调度的对象主要集中在 板材、带钢、无缝管、棒线材等产品上，结合热轧圆钢特 点的批量调度问题的研究成果相对较少． 本文在已有研究的基础上，针对热轧圆钢的生产 特点，在销售订单组批完成和轧制单元划分完毕的前 提下，建立了以最小化设备调整时间、拖期生产惩罚和 钢种跳跃惩罚为优化目标的热轧圆钢批量调度问题模 型，来达到降低生产成本，减少生产延误率和提高客户 响应度，实现最大化利润的目标． 结合问题特征，基于 变邻域搜索技术设计了求解算法，并用实际生产数据 来验证所提出模型和算法的有效性． 1 问题建模 1. 1 问题描述 连轧机是圆钢在热轧阶段的核心设备，一般由粗 轧机组、中轧机组和精轧机组构成，每类机组由不同数 量的轧机构成，从粗轧到中轧，再到精轧，装有不同类 型轧辊的轧机组合在一起，构成了热轧圆钢轧制的孔 型系统． 因此，相对于其他钢铁产品，热轧圆钢的轧制 过程有如下特点: ( 1) 轧制不同规格的圆钢需要的轧机数目不同， 即不同规格的圆钢对应的孔型系统不同; ( 2) 当轧制规格发生变化时，需要进行轧机的安 装与拆卸操作，且需要额外的试轧过程，因此为了保证 产品质量、降低生产成本和提高生产效率，一般要确保 规格相同的圆钢集中轧制; ( 3) 两两轧制规格间的设备调整时间是非对称 的，因而合理的轧制规格序列能有效地提高设备利 用率; ( 4) 根据交货期要求，若轧制单元的完工时间晚 于规定的交货时间，将会产生拖期生产成本; ( 5) 相同钢种的轧制单元应尽可能集中生产，以 节约产能和保证产品质量． 在编制轧制计划时，计划人员首先根据工艺规范 对销售订单进行坯料设计和轧制组批，在不违反能力 约束的条件下，设计得出轧制单元集合，将其作为热轧 阶段的最小批次来组织生产． 在轧制组批完成之后， 需要对轧制单元集合进行生产顺序的排定，使得机器 设备总的调整时间最短，这一过程可以归结为与顺序 相关的单机批调度问题( single machine batch schedu￾ling problem with sequence-dependent setup time) ． 根据 热轧圆钢的轧制特点，本文将轧制单元定义为轧制规 格和钢种相同，以及交货期相同或相近的钢坯集合，也 即可以在一个批次内生产的钢坯序列． 综上所述，热轧圆钢的批量调度问题可以描述为: 假设有 n 个待轧制的轧制单元，每个轧制单元的轧制 规格、钢种、交货期等属性均已知，批量调度问题就是 对轧制单元集合进行合理有效的排序，使得生产过程 中产生的设备调整时间、拖期生产惩罚和钢种跳跃惩 罚最小，其中设备调整时间对于生产成本、生产效率以 及生产连续性有着重要意义． 因此，本文结合实际生 产过程中不同指标重要程度的差异性，采用串联方式 按“设备调整时间→拖期生产惩罚→钢种跳跃惩罚” 的重要程度排序，在求解过程中对三个指标进行串行 寻优． 1. 2 问题模型 热轧圆钢的批量调度问题是一类设备调整时间与 加工顺序有关的单机调度问题，即对轧制单元进行排 序，保证在总的设备调整时间最小的前提下，尽可能使 拖期生产费用和钢种跳跃惩罚最小． 该问题实质上可 以归结为一个扩展型的非对称旅行商问题( asymmetric travelling salesman problem，ATSP) ［11］，其中每个轧制 单元等价于一个城市，任意两个城市之间的距离为两 个轧制单元间的设备调整时间，且呈现非对称特征，则 问题描述如下: 一个旅行商要访问 n 个城市( 轧制单 元) ，要求每个城市( 轧制单元) 都被访问一次且仅一 次，尽可能在某个时间之前被访问，否则将产生延误惩 · 211 ·

柏亮等：基于变邻域搜索的热轧圆钢批量调度多目标优化方法 ·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 ·

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 ·

柏亮等：基于变邻域搜索的热轧圆钢批量调度多目标优化方法 115 算法框架中耗时最多的部分，并且在很大程度上决定 史最优解，即令x=x:然后按照EDD规则将轧制规格 着算法最终的求解质量，因而在设计局部搜索策略时 k∈K内的轧制单元i∈I,按最晚交货期d,不减的顺序 要充分考虑变邻域搜索算法的求解效率。本文在设计 进行排列，再按钢种升序的顺序进行排列：最后计算 局部搜索策略时主要从两个方面进行考虑，即算法采 (x)和(x),并将得到的结果分别作为历史最优拖期 用的局部搜索算子以及搜索策略.首先，结合问题的 生产惩罚和钢种跳跃惩罚 非对称旅行商特征以及在前期大量实验的基础上，并 规则2若(x)=(x),即对于设备调整时间 结合2opt和or-opt两种算子的特点，采用将两种算子 来说，当前解x与历史最优解x同优：进一步判断，按 混合的方式来优化局部搜索过程，每次局部搜索都随 照EDD规则将轧制规格k∈K内的轧制单元i∈I,按 机只选取一种算子.具体如下： 最晚交货期d,不减的顺序进行排列，再按钢种升序的 (1)2opt算子是在当前解上移除两条不相邻的 顺序进行排列，并计算5(x)和(x),其中若（x)> 弧，并添加另外两条新的弧，从而生成一条新的设备调 2(x)或2(x)≤f5(x)且5（x)>f3（x),则令=x, 整时间更小的路径： 即用当前解代替历史最优解：否则，不更新历史最 (2)or-opt算子是将当前解中顺序相连的一些节 优解 点移到同一条路径上的其他位置得到新的设备调整时 规则3若(x,)r。成立时，接受较劣 k),最大寻优次数为MaxIter、初始温度T。、降温迭代 解xa并更新当前解x,即x=x4:其中，r。是区间D,1] 次数n,和降温系数；令i=1,k=1. 上均匀分布的随机数，温度T的初始值为T。,每隔n, Step3邻域构造与局部优化. 次迭代按照T.+1=α·T。来进行更新，α是可设定的降 Step3.I根据Insert算子或Swap算子构造s的 温系数. 邻域结构集合，并在第k个邻域结构内随机生成一个 2.6更新历史最优解 轧制规格序列s,计算关于s的设备调整时间： 在优化设备调整时间的过程中，当历史最优轧制 Step3.2针对s.进行基于2-opt或or-opt的局部 规格序列发生变化时，需要按照规则更新轧制单元的 搜索操作，得到局部最优轧制规格序列5a: 开始时间和结束时间，并更新历史最优的拖期生产惩 Step3.3若sa优于s,则令s=sa,k=1,否则根据 罚和钢种跳跃惩罚.令和⅓分别表示设备调整 模拟退火接受准则判断是否接受5a替代s,若是，则令 时间、拖期生产惩罚和钢种跳跃惩罚的目标函数，x和 k=1,否则令k=(kmod k)+1: x分别为当前解和历史最优解.针对以设备调整时间 Step3.4若sa优于sb,则令s=sa: 为主要优化目标，拖期生产惩罚和钢种跳跃惩罚为次 Step4更新历史解. 要目标的策略，历史解的具体更新规则如下 Step4.1若(x)>∫(x),则按照EDD规则和 规则1若(x)>(x),即对于设备调整时间 钢种升序规则对当前解x进行处理，并令x=x,转 来说，当前解x优于历史最优解x,则用当前解替代历 Step5:

柏 亮等: 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 算法框架中耗时最多的部分，并且在很大程度上决定 着算法最终的求解质量，因而在设计局部搜索策略时 要充分考虑变邻域搜索算法的求解效率． 本文在设计 局部搜索策略时主要从两个方面进行考虑，即算法采 用的局部搜索算子以及搜索策略． 首先，结合问题的 非对称旅行商特征以及在前期大量实验的基础上，并 结合 2-opt 和 or-opt 两种算子的特点，采用将两种算子 混合的方式来优化局部搜索过程，每次局部搜索都随 机只选取一种算子． 具体如下: ( 1) 2-opt 算子是在当前解上移除两条不相邻的 弧，并添加另外两条新的弧，从而生成一条新的设备调 整时间更小的路径; ( 2) or-opt 算子是将当前解中顺序相连的一些节 点移到同一条路径上的其他位置得到新的设备调整时 间更小的路径． 其次，采用 First-improvement［16］ 作为局部搜索改 进策略，确保算法在求解质量和运行时间上达到更好 的平衡，即在求解过程中，一次访问当前解 x 的邻域 解，如果当前访问的邻域解 xn 优于 x，则令 x = xn 并更 新 x 的邻域解，重复该过程直到 x 的所有邻域解都被 访问，最后将求得的 x 作为局部最优解． 2. 5 解的接受准则 为了减小算法陷入局部最优的可能性，一般通过 在求解过程中接受部分较劣解来增大对求解空间的扰 动． 本文采用模拟退火算法( simulated annealing，SA) 中解的接受准则，来控制变邻域搜索算法在一定条件 下接受较劣解． 令 x 为当前解，xd 为当前解 x 经过邻域构造过程 和局部搜索之后得到的局部最优解，计算 Δf = f( xd ) － f( x) ，其中 f( x) 是当前解 x 的目标函数值． 若 Δf ＜ 0， 即局部最优解 xd 优于当前解 x，则用 xd 替代 x 进入下 次迭代; 否则，当 exp( － Δf / T) ＞ r0 成立时，接受较劣 解 xd 并更新当前解 x，即 x = xd ． 其中，r0 是区间［0，1］ 上均匀分布的随机数，温度 T 的初始值为 T0，每隔 nT 次迭代按照 Tn + 1 = α·Tn 来进行更新，α 是可设定的降 温系数． 2. 6 更新历史最优解 在优化设备调整时间的过程中，当历史最优轧制 规格序列发生变化时，需要按照规则更新轧制单元的 开始时间和结束时间，并更新历史最优的拖期生产惩 罚和钢种跳跃惩罚． 令 f1、f2 和 f3 分别表示设备调整 时间、拖期生产惩罚和钢种跳跃惩罚的目标函数，x 和 xb 分别为当前解和历史最优解． 针对以设备调整时间 为主要优化目标，拖期生产惩罚和钢种跳跃惩罚为次 要目标的策略，历史解的具体更新规则如下． 规则 1 若 f1 ( xb ) ＞ f1 ( x) ，即对于设备调整时间 来说，当前解 x 优于历史最优解 xb，则用当前解替代历 史最优解，即令 xb = x; 然后按照 EDD 规则将轧制规格 k∈K 内的轧制单元 i∈Ik 按最晚交货期 di 不减的顺序 进行排列，再按钢种升序的顺序进行排列; 最后计算 f2 ( x) 和 f3 ( x) ，并将得到的结果分别作为历史最优拖期 生产惩罚和钢种跳跃惩罚． 规则 2 若 f1 ( xb ) = f1 ( x) ，即对于设备调整时间 来说，当前解 x 与历史最优解 xb 同优; 进一步判断，按 照 EDD 规则将轧制规格 k∈K 内的轧制单元 i∈Ik 按 最晚交货期 di 不减的顺序进行排列，再按钢种升序的 顺序进行排列，并计算 f2 ( x) 和 f3 ( x) ，其中若 f2 ( xb ) ＞ f2 ( x) 或 f2 ( xb ) ≤f2 ( x) 且 f3 ( xb ) ＞ f3 ( x) ，则令 xb = x， 即用当 前 解 代 替 历 史 最 优 解; 否 则，不 更 新 历 史 最 优解． 规则 3 若 f1 ( xb ) ＜ f1 ( x) ，则不更新历史最优解． 2. 7 算法步骤 综上所述，求解热轧圆钢批量调度问题的算法步 骤如下． Step1 轧制单元预处理． Step1. 1 对每个 i∈I 内的钢坯集合 Vi，初始化最 晚交货期，并获得最晚交货期最早的钢坯 l1 ; Step1. 2 对每个 i∈I，根据公式 di = di 1 + ∑ ni l = 2 pi l 计算轧制单元 i 的最晚交货期; Step1. 3 将轧制单元集合 I 划分为 m 个分组( m ＜ n) ，按 EDD 准则对轧制规格 k 所对应的轧制单元分 组 Ik 包含的轧制单元集合进行处理． Step2 初始化． Step2. 1 利用约束满足算法生成初始解 x0，获得 初始轧制规格序列 s0，令当前轧制规格序列 s = s0，历 史最优轧制规格序列 sb = s0，历史最优解 xb = x0 ; Step2. 2 确定邻域结构集合 Nk ( k = 1，2，…， kmax ) ，最大寻优次数为 MaxIter、初始温度 T0、降温迭代 次数 nT 和降温系数 α; 令 i = 1，k = 1． Step3 邻域构造与局部优化． Step3. 1 根据 Insert 算子或 Swap 算子构造 s 的 邻域结构集合，并在第 k 个邻域结构内随机生成一个 轧制规格序列 sk，计算关于 sk 的设备调整时间; Step3. 2 针对 sk 进行基于 2-opt 或 or-opt 的局部 搜索操作，得到局部最优轧制规格序列 sd ; Step3. 3 若 sd 优于 s，则令 s = sd，k = 1，否则根据 模拟退火接受准则判断是否接受 sd 替代 s，若是，则令 k = 1，否则令 k = ( kmod kmax ) + 1; Step3. 4 若 sd 优于 sb，则令 sb = sd ; Step4 更新历史解． Step4. 1 若 f1 ( xb ) ＞ f1 ( x) ，则按照 EDD 规则和 钢种升序规则对当前解 x 进行处理，并令 xb = x，转 Step5; · 511 ·

116 工程科学学报，第37卷，第1期 Step4.2若∫(x)=∫(x),按照EDD规则和钢 (2)变邻域搜索算法(VNS-I).与VNS-Ⅱ算法 种升序规则对当前解x进行处理，并计算，(x)和 相同，也用变邻域搜索算法优化设备调整时间，但采用 (x):若2(x)>6(x)或2(x)≤5(x)∧3(x)>f3 随机的方式来对轧制单元排序，达到优化拖期生产惩 (x),则令=x,否则转Step5; 罚和钢种跳跃惩罚的目的 Step4.3若f(x)MaxIter,则转Step5.2, 和VNS-Ⅱ算法的参数均设置为：最大寻优次数Max- 否则返回执行Step3; Iter=200;在局部搜索中2opt算子和or-opt算子被选 Step5.2算法停止，输出历史最优解x,作为最 择的概率均设为0.5；模拟退火接收准则中初始温度 终解 T。=l0,每隔n,=MaxIter/10后更新温度，退火系数 3数据实验 a=0.95. 实验数据设置如下：G=6,41=15min,t2= 3.1实验数据与环境 20 min,=10 min. 为了验证本文提出的模型和算法，现以某钢铁厂 本文算法采用Microsoft Visual Ci#编程实现，实验 热轧圆钢生产线的10组实际生产数据为算例进行仿 环境为Core i5/2.50GHz/2GB/Windows7 Ultimate. 真实验.将本文提出的算法记为VNS-Ⅱ算法，为进一 3.2实验结果与分析 步考察算法的求解性能，实验中将其与以下两种算法 针对每个算例分别用三种算法运行10次后取平 比较. 均值，得到的实验结果如表1所示，其中m和n分别代 (1)约束满足算法(CSP).根据文中给出的变量 表轧制规格数和轧制单元数，和分别表示设备 选择规则和值选择规则，选择变量后从变量的值域中 调整时间、拖期生产惩罚和钢种跳跃惩罚的优化值，运 寻找一组满足约束的值赋给变量，然后进行约束传播. 行时间是指VNS-Ⅱ算法的求解时间. 表1实验结果 Table 1 Experimental results 运行 CSP/min VNS-1/min VNS-I/min 算例 m n 时间/s f f左 公 万 f 5 f3 15 60 8.5 1670 16.5 406 1595 23.8 562 1595 10.7 286 2 20 50 10.3 1945 30.0 396 1835 56.7 424 1825 24.3 214 3 25 80 15.8 2110 38.3 460 2000 47.9 540 2000 28.8 283 30 105 23.2 2440 47.2 560 2260 55.0 674 2260 15.7 374 36 245 55.4 2590 124.7 580 2325 140.5 780 2320 104.4 469 6 40 360 63.3 2840 150.5 1176 2515 178.0 1434 2500 96.0 645 > 420 76.5 2906 267.0 1461 2716 311.3 1752 2716 152.5 1074 吃 580 92.0 3149 303.9 1878 2889 388.6 1904 2889 264.8 1342 9 55 675 117.0 3328 385.0 1957 3108 460.4 2136 3108 356.5 1675 10 60 800 142.6 3798 516.6 2156 3508 577.9 2318 3503 486.9 1994 为进一步说明VSⅡ算法的有效性和收敛性，选 取算例5（问题规模为36×245）的计算结果进行展示. 2650 2600 图1给出了设备调整时间随迭代次数的变化曲线. 2550 由上述实验结果可以得到以下结论： 2500 2450 (1)针对不同的问题规模，VNS-Ⅱ算法得到的解 2400 的质量都要优于约束满足问题算法和VNSH算法. 一 2350 始2300 方面，VNS-Ⅱ算法是以约束满足问题算法得到的解作 2250 2200 为初始解进行优化，而约束满足问题算法在求解过程 215 020305080100150180200250300 中采用贪婪策略来优化三个优化指标，容易陷入局部 送代次数 最优解，VNS-Ⅱ算法能够在此基础上利用变邻域搜索 图1设备调整时间变化曲线 算法的特性对解进行优化改善，得到更好的解：另一方 Fig.1 Graph for setup time

工程科学学报，第 37 卷，第 1 期 Step4. 2 若 f1 ( xb ) = f1 ( x) ，按照 EDD 规则和钢 种升序规则对当前解 x 进行处理，并计算 f2 ( x) 和 f3 ( x) ; 若 f2 ( xb ) ＞ f2 ( x) 或 f2 ( xb ) ≤f2 ( x) ∧f3 ( xb ) ＞ f3 ( x) ，则令 xb = x，否则转 Step5; Step4. 3 若 f1 ( xb ) ＜ f1 ( x) ，则转 Step5; Step5 判断终止条件． Step5. 1 令 i = i + 1，若 i ＞ MaxIter，则转 Step5. 2， 否则返回执行 Step3; Step5. 2 算法停止，输出历史最优解 xb 作为最 终解． 3 数据实验 3. 1 实验数据与环境 为了验证本文提出的模型和算法，现以某钢铁厂 热轧圆钢生产线的 10 组实际生产数据为算例进行仿 真实验． 将本文提出的算法记为 VNS--II 算法，为进一 步考察算法的求解性能，实验中将其与以下两种算法 比较． ( 1) 约束满足算法( CSP) ． 根据文中给出的变量 选择规则和值选择规则，选择变量后从变量的值域中 寻找一组满足约束的值赋给变量，然后进行约束传播． ( 2) 变邻域搜索算法( VNS--I) ． 与 VNS--II 算法 相同，也用变邻域搜索算法优化设备调整时间，但采用 随机的方式来对轧制单元排序，达到优化拖期生产惩 罚和钢种跳跃惩罚的目的． 考虑到影响算法的主要因素为算法的参数以及问 题的规模，并经过前期大量数据实验验证，将 VNS--I 和 VNS--II 算法的参数均设置为: 最大寻优次数 Max￾Iter = 200; 在局部搜索中 2-opt 算子和 or-opt 算子被选 择的概率均设为 0. 5; 模拟退火接收准则中初始温度 T0 = 10，每隔 nT = MaxIter /10 后更新温度，退火系 数 α = 0. 95． 实验数据设置如下: Gmax = 6，t1 = 15 min，t2 = 20 min，t3 = 10 min． 本文算法采用 Microsoft Visual C#编程实现，实验 环境为 Core i5 /2. 50GHz /2GB /Windows 7 Ultimate． 3. 2 实验结果与分析 针对每个算例分别用三种算法运行 10 次后取平 均值，得到的实验结果如表 1 所示，其中 m 和 n 分别代 表轧制规格数和轧制单元数，f1、f2 和 f3 分别表示设备 调整时间、拖期生产惩罚和钢种跳跃惩罚的优化值，运 行时间是指 VNS--II 算法的求解时间． 表 1 实验结果 Table 1 Experimental results 算例 m n 运行 时间/ s CSP /min VNS--I /min VNS--II /min f1 f2 f3 f1 f2 f3 f1 f2 f3 1 15 60 8. 5 1670 16. 5 406 1595 23. 8 562 1595 10. 7 286 2 20 50 10. 3 1945 30. 0 396 1835 56. 7 424 1825 24. 3 214 3 25 80 15. 8 2110 38. 3 460 2000 47. 9 540 2000 28. 8 283 4 30 105 23. 2 2440 47. 2 560 2260 55. 0 674 2260 15. 7 374 5 36 245 55. 4 2590 124. 7 580 2325 140. 5 780 2320 104. 4 469 6 40 360 63. 3 2840 150. 5 1176 2515 178. 0 1434 2500 96. 0 645 7 45 420 76. 5 2906 267. 0 1461 2716 311. 3 1752 2716 152. 5 1074 8 50 580 92. 0 3149 303. 9 1878 2889 388. 6 1904 2889 264. 8 1342 9 55 675 117. 0 3328 385. 0 1957 3108 460. 4 2136 3108 356. 5 1675 10 60 800 142. 6 3798 516. 6 2156 3508 577. 9 2318 3503 486. 9 1994 为进一步说明 VNS--II 算法的有效性和收敛性，选 取算例 5( 问题规模为 36 × 245) 的计算结果进行展示． 图 1 给出了设备调整时间随迭代次数的变化曲线． 由上述实验结果可以得到以下结论: ( 1) 针对不同的问题规模，VNS--II 算法得到的解 的质量都要优于约束满足问题算法和 VNS--I 算法． 一 方面，VNS--II 算法是以约束满足问题算法得到的解作 为初始解进行优化，而约束满足问题算法在求解过程 中采用贪婪策略来优化三个优化指标，容易陷入局部 最优解，VNS--II 算法能够在此基础上利用变邻域搜索 算法的特性对解进行优化改善，得到更好的解; 另一方 图 1 设备调整时间变化曲线 Fig． 1 Graph for setup time · 611 ·

柏亮等：基于变邻域搜索的热轧圆钢批量调度多目标优化方法 ·117 面，VNS-Ⅱ算法在优化过程中嵌入了EDD准则和钢 based on constraint satisfaction.Control Decis,2007,22(4):389 种排序准则，使得两个次要优化指标也能得到较好的 (李铁克，郭冬芬.基于约束满足的热轧批量计划模型与算 法.控制与决策，2007,22(4)：389) 优化，因此VNS-Ⅱ能够比VNS-I得到更优秀的解 B] Zhang X J.Lii Z M.Refactoring model and generalized method for (2)对于主要优化指标，VNSH和VNS-HⅡ的优化 a type of scheduling problem based on constraint programming 效果相似，这主要是因为两者都采用变邻域搜索算法 method.Comput Eng Appl,2012,48 (26):219 进行优化，改进效果明显优于约束满足问题算法 (张旭君，吕志民.基于约束规划的一类排序问题通用求解方 (3)对于两个次要优化指标，VNS-Ⅱ算法在优化 法.计算机工程与应用，2012,48(26)：219) 4]Pan CC.Yang G K.A method of solving a large scale rolling 过程中嵌入了EDD准则和钢种排序准则，解的改进效 batch scheduling problem in steel production using a variant of col- 果最好：约束满足问题算法在优化过程中使用了贪婪 umn generation.Comput Ind Eng,2009,56(1):165 策略，改进效果适中：而VNS-I算法使用随机排序方 [5]Yang Y J,Jiang Z Y,Zhang XX.Mathematical model and sol- 式，其改进效果是最差的. ving algorithm for the lot planning of slab hot rolling.J Unir Sci (4)由图1可以看出，随着算法的迭代次数的增 Technol Beijing,2012,34(4):457 加，设备调整时间不断减小，且当迭代次数超过100 (杨业建，姜泽毅，张欣欣.板坯热轧批量计划数学模型及求 解算法.北京科技大学学报，2012,34(4)：457) 后，目标值逐渐趋向于保持稳定，说明VNS一Ⅱ算法在 [6 Liu S X.Model and algorithm for hot rolling batch planning in 优化设备调整时间时具有良好的有效性和收敛性. steel plants.Int J Inf Manage Sci,2010,21 (3):247 (5)随着问题规模的不断增大，VNS-Ⅱ算法所用 7]Jia S J,Yi J,Yang G K,et al.A multi-objective optimisation al- 时间逐渐增加，但即使是对于轧制规格数为60和轧制 gorithm for the hot rolling batch scheduling problem.Int Prod 单元数为800的问题，VNS-HⅡ算法在经过200次迭代 Res,2013,51(3):667 [8]Tang L X,Huang L.Optimal and near-optimal algorithms to roll- 之后，获得较满意解的平均时间是142.6s,在一定程 ing batch scheduling for seamless steel tube production.Int Prod 度上能够满足实际应用需求 Econ,2007,105(2):357 4结论 [9]Li L,Huo J Z.Multi-objective flexible job-shop scheduling prob- lem in steel tubes production.Syst Eng Theory Pract,2009,29 批量调度是钢铁企业生产管理中的关键问题，在 (8):117 理论和实践中具有重要的研究意义.针对热轧圆钢的 (李琳，霍佳震.钢管生产计划中的多目标柔性Job一shop调 度问题.系统工程理论与实践，2009,29(8)：117) 批量调度问题，本文结合热轧圆钢的实际生产特点，充 Wang X,Yang C H,Qin B.Multi-objective hybrid optimization 分考虑了各类工艺约束和因素，将问题归结为扩展型 of lot scheduling for bar mill process.Control Decis,2006,21 的非对称旅行商问题，并在此基础上建立了以最小化 (9):996 设备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化 (王欣，阳春华，秦斌.棒线材轧制批量调度多目标混合优 目标的数学模型.通过分析问题的求解特点，设计了 化.控制与决策，2006,21(9)：996) 一种嵌入EDD准则的变邻域搜索算法.算法采用约 [11]Roberti R,Toth P.Models and algorithms for the asymmetric 束满足技术生成初始可行解：利用变邻域搜索算法来 traveling salesman problem:an experimental comparison.EURO J Transp Logist,2012,1(1):113 优化轧制规格序列，以保证设备调整时间最小：在变邻 [12]Hansen P,Mladenovic N.Variable neighborhood search:princi- 域搜索优化过程中，用EDD准则和钢种排序准则来优 ples and applications.Eur J Oper Res,2001,130(3):449 化拖期生产惩罚和钢种跳跃惩罚，保证算法的全局优 [3] Imran A,Salhi S,Wassan N A.A variable neighborhood-based 化能力.仿真实验表明，本文提出的算法对热轧圆钢 heuristic for the heterogeneous fleet vehicle routing problem.Eur 的批量调度问题具有较好的求解效果，且计算效率满 J0 per Res,2009,197(2):509 足实际应用的需求 [14] Fellows M,Friedrich T,Hermelin D,et al.Constraint satisfac- tion problems:convexity makes AllDifferent constraints tracta- ble.Theor Comput Sci,2013,472:81 参考文献 05] Zhang W X,Li T K.Modelling and algorithm for the slab desig- [1]Liu Q,Bai S H,Lu J H,et al.Production plan schedule for the ning problem based on constraint satisfaction.I Unit Sci Technol casting-tolling process in BOF special steel plants.J Unie Sci Beijing,2011,33(5):641 Technol Beijing,2008,30(5):566 (张文学，李铁克，基于约束满足的板坯设计模型与求解方 (刘青，白素宏，卢军辉，等.转炉特钢流程连铸一轧钢生产排 法.北京科技大学学报，2011,33(5)：641) 产系统.北京科技大学学报，2008,30(5)：566) [16]Hansen P,Mladenovic N.First vs.best improvement:an empir- 2]Li T K,Guo D F.Model and algorithm for hot-rolling batch plan ical study.Discrete Appl Math,2006,154(5)802

柏 亮等: 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 面，VNS--II 算法在优化过程中嵌入了 EDD 准则和钢 种排序准则，使得两个次要优化指标也能得到较好的 优化，因此 VNS--II 能够比 VNS--I 得到更优秀的解． ( 2) 对于主要优化指标，VNS--I 和 VNS--II 的优化 效果相似，这主要是因为两者都采用变邻域搜索算法 进行优化，改进效果明显优于约束满足问题算法． ( 3) 对于两个次要优化指标，VNS--II 算法在优化 过程中嵌入了 EDD 准则和钢种排序准则，解的改进效 果最好; 约束满足问题算法在优化过程中使用了贪婪 策略，改进效果适中; 而 VNS--I 算法使用随机排序方 式，其改进效果是最差的． ( 4) 由图 1 可以看出，随着算法的迭代次数的增 加，设备调整时间不断减小，且当迭代次数超过 100 后，目标值逐渐趋向于保持稳定，说明 VNS--II 算法在 优化设备调整时间时具有良好的有效性和收敛性． ( 5) 随着问题规模的不断增大，VNS--II 算法所用 时间逐渐增加，但即使是对于轧制规格数为 60 和轧制 单元数为 800 的问题，VNS--II 算法在经过 200 次迭代 之后，获得较满意解的平均时间是 142. 6 s，在一定程 度上能够满足实际应用需求． 4 结论 批量调度是钢铁企业生产管理中的关键问题，在 理论和实践中具有重要的研究意义． 针对热轧圆钢的 批量调度问题，本文结合热轧圆钢的实际生产特点，充 分考虑了各类工艺约束和因素，将问题归结为扩展型 的非对称旅行商问题，并在此基础上建立了以最小化 设备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化 目标的数学模型． 通过分析问题的求解特点，设计了 一种嵌入 EDD 准则的变邻域搜索算法． 算法采用约 束满足技术生成初始可行解; 利用变邻域搜索算法来 优化轧制规格序列，以保证设备调整时间最小; 在变邻 域搜索优化过程中，用 EDD 准则和钢种排序准则来优 化拖期生产惩罚和钢种跳跃惩罚，保证算法的全局优 化能力． 仿真实验表明，本文提出的算法对热轧圆钢 的批量调度问题具有较好的求解效果，且计算效率满 足实际应用的需求． 参 考 文 献 ［1］ Liu Q，Bai S H，Lu J H，et al． Production plan schedule for the casting-rolling process in BOF special steel plants． J Univ Sci Technol Beijing，2008，30( 5) : 566 ( 刘青，白素宏，卢军辉，等． 转炉特钢流程连铸--轧钢生产排 产系统． 北京科技大学学报，2008，30( 5) : 566) ［2］ Li T K，Guo D F． Model and algorithm for hot-rolling batch plan based on constraint satisfaction． Control Decis，2007，22( 4) : 389 ( 李铁克，郭冬芬． 基于约束满足的热轧批量计划模型与算 法． 控制与决策，2007，22( 4) : 389) ［3］ Zhang X J，Lü Z M． Ｒefactoring model and generalized method for a type of scheduling problem based on constraint programming method． Comput Eng Appl，2012，48( 26) : 219 ( 张旭君，吕志民． 基于约束规划的一类排序问题通用求解方 法． 计算机工程与应用，2012，48( 26) : 219) ［4］ Pan C C，Yang G K． A method of solving a large scale rolling batch scheduling problem in steel production using a variant of col￾umn generation． Comput Ind Eng，2009，56( 1) : 165 ［5］ Yang Y J，Jiang Z Y，Zhang X X． Mathematical model and sol￾ving algorithm for the lot planning of slab hot rolling． J Univ Sci Technol Beijing，2012，34( 4) : 457 ( 杨业建，姜泽毅，张欣欣． 板坯热轧批量计划数学模型及求 解算法． 北京科技大学学报，2012，34( 4) : 457) ［6］ Liu S X． Model and algorithm for hot rolling batch planning in steel plants． Int J Inf Manage Sci，2010，21( 3) : 247 ［7］ Jia S J，Yi J，Yang G K，et al． A multi-objective optimisation al￾gorithm for the hot rolling batch scheduling problem． Int J Prod Ｒes，2013，51( 3) : 667 ［8］ Tang L X，Huang L． Optimal and near-optimal algorithms to roll￾ing batch scheduling for seamless steel tube production． Int J Prod Econ，2007，105( 2) : 357 ［9］ Li L，Huo J Z． Multi-objective flexible job-shop scheduling prob￾lem in steel tubes production． Syst Eng Theory Pract，2009，29 ( 8) : 117 ( 李琳，霍佳震． 钢管生产计划中的多目标柔性 Job--shop 调 度问题． 系统工程理论与实践，2009，29( 8) : 117) ［10］ Wang X，Yang C H，Qin B． Multi-objective hybrid optimization of lot scheduling for bar mill process． Control Decis，2006，21 ( 9) : 996 ( 王欣，阳春华，秦斌． 棒线材轧制批量调度多目标混合优 化． 控制与决策，2006，21( 9) : 996) ［11］ Ｒoberti Ｒ，Toth P． Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison． EUＲO J Transp Logist，2012，1( 1) : 113 ［12］ Hansen P，Mladenovic N． Variable neighborhood search ＇ : princi￾ples and applications． Eur J Oper Ｒes，2001，130( 3) : 449 ［13］ Imran A，Salhi S，Wassan N A． A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem． Eur J Oper Ｒes，2009，197( 2) : 509 ［14］ Fellows M，Friedrich T，Hermelin D，et al． Constraint satisfac￾tion problems: convexity makes AllDifferent constraints tracta￾ble． Theor Comput Sci，2013，472: 81 ［15］ Zhang W X，Li T K． Modelling and algorithm for the slab desig￾ning problem based on constraint satisfaction． J Univ Sci Technol Beijing，2011，33( 5) : 641 ( 张文学，李铁克． 基于约束满足的板坯设计模型与求解方 法． 北京科技大学学报，2011，33( 5) : 641) ［16］ Hansen P，Mladenovic N． First vs． best improvement ＇ : an empir￾ical study． Discrete Appl Math，2006，154( 5) : 802 · 711 ·