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

工程科学学报，第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,)<(x),则不更新历史最优解 间更小的路径. 2.7算法步骤 其次，采用First-improvement作为局部搜索改 综上所述，求解热轧圆钢批量调度问题的算法步 进策略，确保算法在求解质量和运行时间上达到更好 骤如下 的平衡，即在求解过程中，一次访问当前解x的邻域 Sepl轧制单元预处理. 解，如果当前访问的邻域解x。优于x,则令x=x.并更 Sepl.1对每个i∈I内的钢坯集合V,初始化最 新x的邻域解，重复该过程直到x的所有邻域解都被 晚交货期，并获得最晚交货期最早的钢坯1，： 访问，最后将求得的x作为局部最优解 2.5解的接受准则 Sepl.2对每个ie,根据公式d,=d+∑ 为了减小算法陷入局部最优的可能性，一般通过 计算轧制单元i的最晚交货期： 在求解过程中接受部分较劣解来增大对求解空间的扰 Stepl.3将轧制单元集合I划分为m个分组(m 动.本文采用模拟退火算法(simulated annealing,SA) <n),按EDD准则对轧制规格k所对应的轧制单元分 中解的接受准则，来控制变邻域搜索算法在一定条件 组I,包含的轧制单元集合进行处理. 下接受较劣解. Step2初始化. 令x为当前解，x:为当前解x经过邻域构造过程 Step2.1利用约束满足算法生成初始解x。,获得 和局部搜索之后得到的局部最优解，计算△f=∫(x)- 初始轧制规格序列s。,令当前轧制规格序列s=5。,历 f(x),其中f(x)是当前解x的目标函数值.若△<0， 史最优轧制规格序列s。=。,历史最优解x=x。: 即局部最优解xa优于当前解x,则用xa替代x进入下 Step2.2确定邻域结构集合N(k=1,2,…, 次迭代；否则，当exp(-△f/T)>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 ·