·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 ·