热轧批量调度是轧钢生产管理的核心内容,是根据轧制工艺约束和客户需求对轧件进行组批和排序的过程,其结果的好坏直接影响产品质量和生产效率。传统热轧批量调度中,机器看作连续可用的,忽略机器故障、检修等影响,在这种条件下获得的批量生产执行计划,与实际生产结果具有一定的偏差。热轧实际生产中,机器受到高温、高压的影响会有不同程度的损耗,为保证生产正常运行,需要占用生产时间对机器进行检修维护,造成对批量调度的影响。圆钢生产具有典型热轧批量生产特点,机器故障、检修计划会影响生产批量调度,而刚性检修计划不能实现机器最优利用率、降低生产效率,因此,在圆钢热轧生产管理中,考虑机器柔性检修对批量调度的影响,制定合理的热轧批量调度计划,对有效提高企业生产优化水平具有重要意义。

关于热轧批量调度研究主要有:文献[1]针对轧钢厂精轧工序提出多厂通用的优化模型,用于描述板带、型钢和钢管等的热轧批量调度问题;文献[2, 3]在此基础上将模型扩展,对板材和钢管的热轧批量调度问题进行深入研究,结合二者不同的热轧生产工艺,分别制定板材热轧组批计划和考虑调整时间的钢管轧批顺序计划,有效解决板材和钢管的生产优化;文献[4]考虑棒线材的热轧生产特点,以订单为基本组织单元,将热轧批量调度问题分为组批、轧批排序2个阶段,并针对轧批排序过程,以最小化批次之间的调整时间和调整费用为目标,实现生产效率和生产效益的同时优化。机器检修作为影响热轧批量调度的重要因素,可以分为定期检修和柔性检修2种方式^[5]。不同的检修方式对生产调度的影响不同^[6],在制定批量调度计划时,需要根据不同的检修方式制定不同的优化策略,文献[7]针对钢管生产中存在定期产线检修的情况,将检修计划作为约束条件,在检修外的时间区间内对合同进行排产,有效解决带有生产路径柔性选择的调度优化问题;文献[8]在2个阶段流水车间批量调度中,考虑热轧阶段机器损耗对产品质量的影响,将带有柔性时间窗的机器检修作为生产约束条件建立问题模型,并用遗传算法实现批量和检修的协调调度优化；文献[9]将热轧批量调度问题描述为多目标奖金收集车辆路径问题,并根据逼近理想点排序法(TOPSIS)进行有效计算；文献[10]考虑连铸和热轧一致批量调度,提高热送率,利用改进遗传算法进行有效求解。上述文献对热轧批量调度进行系统研究,利用智能化方法解决批量调度问题,并考虑检修计划对调度的影响,针对多种热轧产品进行多目标优化的批量调度研究,但是针对具有柔性检修计划的热轧圆钢批量调度问题研究较少。

根据圆钢热轧生产特点,针对热轧批量排序阶段,考虑生产过程中存在柔性检修计划的情况,研究机器检修对批量生产的影响,以最小化最大完工时间和订单提前及拖期总时长为目标建立批量调度优化模型,根据问题特征提出改进的多目标粒子群优化算法实现问题求解,通过数据实验验证算法的可行性和有效性。

圆钢热轧生产中,为保证生产质量要制定柔性轧机检修计划,即将检修计划设定在1个大于检修时长的时间段内执行。该问题是存在柔性检修计划条件下制定批量生产计划的过程,即根据检修计划的可行时间段,对检修和批量进行调度,确定批量生产顺序和检修计划的执行时间。同时,轧制不同规格的批量需要机架类型和数量不同,并且拆装机架的时间也不同,使得不同批量加工顺序产生不同机器调整时间;此外,机器检修占据生产时间,不同的检修执行时间导致批量生产时间也不同。因此,在制定批量调度计划时同时优化批量加工顺序和检修时间,能够提高生产效率和效益。

图 1为具有柔性检修计划的批量调度示意图,其中,检修的柔性执行时间区间为^{[13, 19]},检修所需时长为5。图 1(a)、图 1(b)和图 1(c)为3种不同的调度计划产生不同的结果:在图 1(a)和图 1(b)2种调度计划中,保持批量顺序相同,调整检修计划执行时间使得各批量(J1、J2和J3)的完工时间和总完工时间产生变化,即将检修计划的执行时间提前导致批量J3的完工时间和总完工时间缩短;图 1(c)调度计划是在保持与图 1(a)中检修计划时间相同的情况下对批量顺序进行调整,使得总完工时间提前。由3种不同的调度结果可以发现,批量顺序和检修时间的确定对生产能够产生影响,并且二者之间存在相互影响和相互制约的关系,因此,在制定生产计划时需要考虑二者的协调优化。

图 1 带有检修计划的批量调度示意图 Fig. 1 Schematic diagram of batch scheduling with maintenance plan

图选项

考虑生产和交货两方面的优化需求,企业在制定调度计划时,主要考虑以下方面:①尽可能地最早完工,减少机器闲置时间,以便提高产能利用率;②最大限度地按照交货时间安排批量生产,提高交货准时性。因此,圆钢热轧生产过程以最小化最大完工时间和订单提前拖期总时长为优化目标,主要考虑以下约束:①机器检修计划必须安排在事先规定好的时间区间内执行;②机器检修和批量加工都不可被中断,保持生产过程的连续性;③不同规格的批量在连续加工过程中需要进行机器调整;④同种规格的批量之间遵循钢种优先级规则,即优先级较高的批量优先加工。

问题假设如下:

假设1 机器检修完成后处于准备加工状态时,在加工下一批量时不考虑机器调整。

假设2 机器检修时长不小于最大批量加工时长以及最大机器调整时长。

1) 符号定义

H为轧批集合,H={1,2,…,k};z为轧批编号,z∈H;z′为不同于z的轧批编号,z′∈H;I_z为轧批z包含的订单集合,I_z={1,2,…,n_z};i为订单编号,为订单i的要求交货时间窗;pb_z为批量z的轧制时长;gb_z为批量z的钢种;o(gb_z)和o(gb_z′)分别为批量z和批量z′的钢种优先级;[SM,EM]为机器检修的柔性时间区间;DM为机器检修所需的时长;s_zz′为批量z和批量z′连续生产所需要的机器调整时间;td为拆机架的单位时间;tu为安装机架的单位时间;tr为试轧时间;a_z为轧批量z对应的产品规格所需要的机架数;a_zz′为批量z和批量z′对应的规格所需的相同机架数;Q为机器调整单位时间成本;ε为任意小的正数。

2) 变量定义

x_zz′为0-1决策变量。若批量z′紧邻批量z之后加工,则变量取值为1,否则取值为0;y_zz′为0-1决策变量。若批量z′紧邻批量z之后且二者之间存在检修计划,变量取值为1,否则取值为0;ST为机器检修的开始时间;sb_z为批量z的轧制开始时间;Cb_z为批量z的轧制结束时间。

3) 数学模型

目标函数式(1)表示最小化最大完工时间;目标函数式(2)表示最小化订单的提前和拖期总时间,这里,订单完工时间取订单所在批量的完工时间;约束式(3)表示2个变量之间的关系,即检修计划仅允许插入到2个相邻批量之间;约束式(4)和约束式(5)表示机器检修必须安排在检修的可执行时间区间内;约束式(6)和约束式(7)表示机器检修和批量加工之间相互独立,具有不可被中断的属性;约束式(8)定义了相邻批量之间连续加工所需的机器调整时间;约束式(9)表示2个相邻批量之间的加工时间关系,同一时刻机器只能对同一批量进行加工,若两批量之间存在检修计划,则不需要进行机器调整,否则,需要考虑机器调整时间;约束式(10)定义了批量的完工时间;约束式(11)表示规格相同的2个相邻批量之间加工先后顺序要满足钢种的优先级关系,即先加工的批量钢种优先级不能低于后加工的批量钢种优先级;约束式(12)和式(13)为变量取值约束。

多变量、多约束特征、多目标特性让问题变得复杂,精确算法难以求解。粒子群算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart^[11]提出的群体智能优化算法,具有操作简单、易于实现及收敛速度快等优点,在很多优化问题中得到成功应用^{[12, 13]}。针对问题变量的离散特征,需要改进粒子群算法,结合精英策略和遗传操作方法,提出改进的多目标粒子群优化算法(Improved Multi-objective Particle Swarm Optimization,IMPSO)来求解。

问题求解目的是确定满足生产约束条件,使得目标函数达到最优的热轧批量生产序列和检修计划执行时间,求解过程的关键在于调整批量之间的先后加工顺序,进而根据批量序列确定机器检修时间。为了便于算法实现,粒子编码形式采用十进制的自然顺序排列的批量顺序。例如,8个批量1~8的先后加工顺序为2→6→1→8→7→3→5→4,则粒子编码表示为x=(2,6,1,8,7,3,5,4)。

由上述编码规则可知,粒子是按自然顺序排列的批量序列,若要实现问题的完整求解,还需对粒子进行解码操作。结合问题的求解特点,粒子的解码操作主要分为2个方面:批量加工时间粗计算、确定检修计划时间。以粒子x=(z₁,z₂,…,z_k)(其对应的编码为z₁~z_k的k个不同批量的加工顺序为z₁→z₂→…→z_k)为例,对其进行的解码操作如下:

1) 批量加工时间粗计算

根据粒子代表的批量加工顺序,在不考虑柔性检修计划的情况下,初步计算每个批量的开始和结束时间。对处于首位的批量z₁,由于机器处于准备加工状态,不需考虑机器调整时间,其加工开始时间即为计划开始时间sb_z1=0,完工时间为Cb_z1=pb_z1;对粒子中其他位置的批量z_j(j=2,3,…,k),机器处于上一个批量z_j-1完工状态,需要根据二者之间的规格判断是否进行机器调整,并计算机器调整时间s_zj-1z_j,则批量z_j的开始和结束时间分别为sb_zj=Cb_zj-1+s_zj-1z_j,Cb_zj=sb_zj+pb_zj。

2) 确定检修计划时间

由于机器检修与批量加工都具有不可被中断的属性,根据批量序列确定机器检修时间的具体过程如下:

① 确定检修在批量序列中所有可能的插入位置。根据批量的完成时间和检修计划的柔性时间区间选择位置上下界。位置下界,选择批量序列中满足条件Cb_zj-1z_j≥SM的批量z_j所处的位置j为下界;位置上界,将满足条件Cb_zj′≤EM-DM∧Cb_zj′+1>EM-DM的批量z_j′所在的位置j′固定为上界。检修计划在批量序列中所有可能的位置用集合表示为L={j,j+1,…,j′}。

② 固定检修时间并修正批量开始和结束时间。根据上一步得到的结果,令l从j到j′变化,将检修计划插入到位置l,即批量z_l、z_l+1之间,形成检修计划和批量混合的序列q_l,取机器检修计划的开始时间为ST=max{Cb_zl,SM},结束时间为ST+DM;由于检修占用了部分生产时间,需要对q_l中在检修后加工的批量重新计算开始和结束时间,根据检修前后的时间变化,计算后移时间差Δ=(ST+DM-Cb_zl)-s_zlzl+1,对于在检修计划后加工的批量z_h(h=l+1,l+2,…,k),其开始和结束时间分别更新为:sb_zh←sb_zh+Δ,Cb_zh←Cb_zh+Δ。对每个q_l(l=j,j+1,…,j′),计算目标函数值,并分析彼此间的支配关系,选择处于非支配地位的1个,其对应的检修计划时间和批量的开始和结束时间即为粒子解码后的结果。

首先,借鉴混沌序列的遍历性原理^[14],由混沌运动生成遵循自身变化规律且具有多样性特点的权重系数,并采用加权和的方式将多目标转化为单目标的适应度函数;与此同时,对于目标函数可能具有不同数量级的情况,对目标函数进行量纲化处理。

其次,基于问题的求解目标,本文采用最早工期优先(Earliest Due Date,EDD)和最短加工时间优先(Shortest Processing Time,SPT)2种规则分别对批量进行优先级排序形成2个初始序列,为了保持种群多样性,其他粒子采用随机方式排序形成不同的初始序列。

生成 N 个初始粒子的具体步骤如下:

算法1 基于混沌加权适应度计算的插入式算法

步骤1 设置初始权重系数w₁⁰(0≤w₁⁰≤1),按照批量交货期(取值于该批量包含的所有订单的平均交货时间,即 为批量包含的订单数量)由早到晚、加工时长由大到小的规则对批量进行初始排序形成2个序列q₁和q₂,并采用随机方式生成N-2个序列q₃,q₄,…,q_N,由这些序列构成序列集合Q={q₁,q₂,…,q_N}。

步骤2 令i从1到N变化,对序列q_i,采用Logistic映射作为混沌系统生成目标函数式(1)的权重系数w₁ⁱ=μw₁^i-1(1-w₁^i-1),μ∈(2,4］,并计算目标函数式(2)的权重系数w₂ⁱ=1-w₁ⁱ,执行步骤3。

步骤3 在序列q_i中,首先选择前两个批量进行排序形成2个子序列q_i1²和q_i2²,在对目标函数量纲化处理的基础上从中选择待操作序列 =min_f{q_i1²,q_i2²}(min _f{a,b}表示从a和b2个序列中选择使适应度函数值f=w₁ⁱf ′₁+w₂ⁱf ′₂较小者),执行步骤4。

步骤4 令h从3到N变化,将第h个批量插入到序列 中所有可能的h个位置形成h个序列{q_i1^h,q_i2^h,…,q_ih^h},并更新 =min _f{q_i1^h,q_i2^h,…,q_ih^h},直到h=N,则将 经过编码形成第i个粒子,若h>N,则令i←i+1,返回执行步骤2。

由问题模型可知,导致粒子不可行的关键因素是钢种优先级约束,即约束式(11),因此,为了保证算法的有效性,对违背约束条件式(11)的不可行粒子需要设计一定的修复规则进行修复,从而改善粒子的可行度。对粒子x=(z₁,z₂,…,z_k),若其中的某些批量之间的顺序违背钢种优先级关系,则采用下述方法进行修复:

确定个体x中满足条件o(g_zi)<o(g_zi+1)∧s_zizi+1=0的相邻分量z_i和z_i+1,交换z_i和z_i+1的先后顺序,继而重复寻找满足条件o(g_zi)<o(g_zi+1)∧s_zizi+1=0的所有相邻分量并交换先后顺序,直到不存在任意2个相邻分量违背钢种优先级关系。

为了避免精英集合中非支配个体的过量增加导致的低运算效率,需要对精英集合规模进行限制,即通过设置1个固定的规模数值r,规定精英集合规模不超过该数值,即若精英集合为A,则有|A|≤r。对粒子群P采用精英策略进行优秀个体保留的具体操作为:将种群P中的所有非支配解复制到精英集合A中,同时删除精英集合中的重复个体和被支配个体,实现对精英集合的更新。集合A经过更新操作后,其规模会有所变化,为保证集合的精英特性不被破坏,对A进行如下操作:

① 若|A|≤r,则保持A不变。

② 若|A|>r,则对A进行删减操作,即通过一定的个体评价方法选择A中的|A|-r个体进行删除以使其达到规模r。

根据文献[15]中Nondominated Sorting Genetic Algorithm-Ⅱ(NSGA-Ⅱ)算法的拥挤度的思想,对A中的所有个体进行拥挤度计算,并通过拥挤度的大小决定个体优劣,将精英集中密集的劣势个体进行删除从而保留分散个体。

个体极值和全局极值的选择,不同于单目标粒子群算法中选择目标值最大或最小的解,而是要选择处于Pareto前沿的精英解,进而引导粒子向最优非支配前沿进化。

1) 个体极值(pbest)选取策略:个体极值选取采用基于Pareto支配关系的选择方法,即将当前粒子x_i与个体极值pbest进行对比,若x_i不被pbest支配,则将个体极值更新为x_i,即pbest←x_i,否则pbest保持不变。

2) 全局极值(gbest)选取策略:通过精英策略得到精英集合后,每个粒子的全局极值从精英集合中选择,为了促进粒子向Pareto最优前沿分散区域优化,采用文献[16]中的σ方法,通过计算粒子与精英集合中所有粒子的σ距离并选择距离最小者作为该粒子的全局极值,实现gbest的更新。粒子间的σ距离计算如下:

计算粒子x的σ值:

对种群中的粒子x_i∈P,其与精英集中的每个粒子x_j∈A的σ距离表示为

算法编码用对批量进行自然顺序排列的方式,粒子具有离散特征,为有效实现粒子更新,借鉴文献[17]中的更新方法,将粒子对应的个体极值和全局极值分别进行交叉并对自身进行变异,从交叉和变异后的后代中选择最优者作为更新结果。将第t代种群中第i个粒子更新到第t+1代的公式为

求解问题的IMPSO算法步骤如下。

算法2 IMPSO算法

步骤1 初始化

步骤1.1 令迭代次数t=0,设置种群规模为N,精英集规模最大为r,变异操作概率P_m,设置最大迭代次数为Iter。

步骤1.2 采用基于混沌加权适应度计算的插入式算法(算法1)得到初始粒子群P₀={x₁⁰,x₂⁰,…,x_N⁰},并设置1个空的精英集合A=∅。

步骤2 不可行粒子修复

对每个粒子x_i^t∈P_t(P_t和x_i^t分别代表第t代的种群和种群中第i个粒子),根据约束条件式(11)判断其可行性,若不可行,则采用修复策略进行修复。

步骤3 精英集更新

步骤3.1 对P_t中的粒子进行优劣对比,确定粒子间的支配关系。

步骤3.2 选择P_t中的所有非支配粒子,复制到精英集合A中,采用精英策略实现A的更新。

步骤4 选取个体极值与全局极值

步骤4.1 将粒子x_i^t∈P_t与当前个体极值pbest_i进行对比,选择处于非支配地位的1个作为新的pbest_i。

步骤4.2 根据式(14),计算粒子x_i^t∈P_t和精英集合中的每个个体x_j∈A(j=1,2,…,|A|)的σ值,进而按式(15)计算x_i^t与x_j的σ距离,选择距离最小者x_i^A={x_j∈A|min{σ(x_i^t,x_j)}},更新x_i^t的全局极值,即gbest_i←x_i^A。

步骤5 更新粒子群

步骤5.1 将个体x_i^t∈P_t与其个体极值pbest_i和全局极值gbest_i分别进行交叉操作,得到4个交叉结果:pbest_i-x_i^t=pb₁,pb₂；gbest_i-x_i^t=gb₁,gb₂。

步骤5.2 随机生成数值r_m∈(0,1),将其与P_m比较,若r_m≤P_m,则对x_i^t进行变异得到x-_i^t,否则,不进行变异操作。

步骤5.3 根据式(16),对临时个体pb₁,pb₂,gb₁,gb₂,x_i^t进行优劣对比,确定支配关系,选择处于非支配地位的个体对x_i^t实现更新,若存在多个处于非支配地位的临时个体,则从中随机选择一个更新到x_i^t。

步骤6 终止条件判断

步骤6.1 令t=t+1,若t>Iter,执行步骤6.2,否则返回执行步骤2。

步骤6.2 输出精英集合A中的所有解,算法结束。

本文采用Microsoft Visual C#在Pentium 4.1/2.90 GHz/2.00 GB/Windows 7环境中编程实现IMPSO算法。结合钢铁企业生产实际,订单、批量等实验数据以及与问题约束条件相关的生产参数等从国内某特钢企业实际生产数据进行采集筛选。实验数据主要包括产品规格、钢种以及钢种优先级、每个规格对应的热轧机架类型和数量、机器检修维护时间以及机架切换的单位时间(其中tu=10 min,td=5 min,tr=20 min)等,实验前将这些生产信息整理成模型参数。实验根据批量规模k的不同分为6组实例进行验证:k=10,20,30,50,100,150,每组生成10个算例。

为了更好地验证IMPSO算法的求解性能,实验中将其与多目标优化算法中应用最为普遍的NSGA-Ⅱ算法和Decreasing order with First Fit(DFF)算法^[18]进行对比。2种算法的参数及对比方式设置如下:IMPSO算法中,种群规模N=100,精英集合规模最大为r=50,变异操作概率P_m=0.25;在NSGA-Ⅱ算法中,种群规模与IMPSO算法相同,初始种群采用随机方式生成,采用二元锦标赛方法选择个体进入交配池,交叉、变异等遗传操作方法与IMPSO算法中的相同。以上算法的最大迭代次数为Iter=100。

对每个算例,采用随机方式从算法所得的所有非支配解中选取1个解作为其最终结果,得到的实验结果见表 1，其中f₁和f₂为目标函数。

由表 1的实验结果可以得到:

1) 针对不同规模的订单和批量数量,除第1组k=10的实例外,目标函数f₁和f₂根据IMPSO算法均能获得较NSGA-Ⅱ算法更优的解,能够实现2个目标的同时优化。这是因为：一方面,IMPSO算法在初始阶段采用一定的优化方法(算法1)获取初始解,比NSGA-Ⅱ基于随机方式生成的初始解具有一定的个体优越性;另一方面,IMPSO和NSGA-Ⅱ虽然都是基于遗传操作实现个体更新,但IMPSO采用个体与极值进行交叉的方式并具有优秀个体筛选的过程,比NSGA-Ⅱ算法中仅在普通个体间进行交叉更容易得到优秀解。目标函数f₁和f₂在其他2种算法的求解效果都好于DFF算法。

2) 在求解效率上,IMPSO算法的求解时间要多于NSGA-Ⅱ算法和DFF算法,计算效率相对较低,这是由于IMPSO在进行粒子更新时有对个体极值、全局极值选择以及对遗传操作结果筛选的过程。即便如此,对于普通规模的批量调度问题(k=150),算法仍然能够在7 min内实现较满意的求解,能够满足批量调度的实际应用需求。

由于求解效果的比对,选取IMPSO算法和NSGA-Ⅱ算法进一步说明算法的有效性,对每组实验的求解结果分别采用不同的性能评价指标进行评价:

1) 质量指标(γ):用于衡量算法所得的解集逼近Pareto最优解的程度。由于问题的Pareto最优解无法事先得知,这里通过将所有参与对比的算法所得的精英集合(IMPSO求得的A_IMPSO和NSGA-Ⅱ求得的A_NSGA-Ⅱ)进行合并,并删除重复个体和被支配个体,从而形成1个参照Pareto最优解集,记为D。计算每个算法(IMPSO和NSGA-Ⅱ)所得的非支配解数量在D中的覆盖比例,即为该算法的质量指标。

2) 分布均匀性指标(SP):主要用于描述算法求解结果在空间上的分布均匀性,解分布越均匀表明算法求解性能越好。采用文献[16]中分布均匀性指标SP,SP值越小表明算法的求解结果分布越均匀。

3) 分布广泛性指标(η):用于表述算法求解结果在空间上的分布分散性,解的分散性越好说明算法的求解效果更好。对解集D′(表示不同算法计算所得的非支配解集D_IMPSO或D_NSGA)计算其分布广泛性指标的公式为

表 2给出了2种算法在不同规模的实例中计算所得结果的指标对比。此外,为了更直观地观察非支配解的分布,以批量规模为k=50为例,从2种算法所得的所有非支配解(染色体)中分别任选10个进行目标函数值对比,结果如图 2所示。

图 2 IMPSO与NSGA-Ⅱ计算所得非支配解分布 Fig. 2 Nondominated solution distribution of IMPSO and NSGA-Ⅱ

图选项

从表 2的性能指标对比结果可以看出,对所有的算例,IMPSO算法相较于NSGA-Ⅱ算法均能够获得更多高质量的非支配解,并且具有更好的分布均匀性和广泛性;图 2中针对k=50的算例的求解结果表明,IMPSO算法的计算结果具有更好的分布性,且相较于NSGA-Ⅱ能够获得更接近Pareto最优解的非支配解。因此,IMPSO算法在求解圆钢热轧批量调度问题上具有较强的优越性,能够取得较好的求解效果。

本文建立了多目标热轧批量调度模型,提出改进多目标粒子群算法实现问题求解。算法采用混沌加权适应度计算的插入式方法生成初始粒子群,设计解码规则对粒子进行解码操作,从而得到问题的完整解。在求解过程中,得到:

1) 修复策略对群体中存在的不可行粒子进行修复,保证解在可行域内。

2) 精英策略实现优秀个体在迭代过程中的延续,并为种群中的个体提供多样化的全局极值。

3) 针对问题的离散特征,使用遗传操作方式进行粒子迭代更新,实现了种群最优化。

最后,以某特钢企业生产数据为基础进行仿真实验,结果表明模型和算法能够有效求解圆钢热轧批量调度问题。