天车是炼钢车间钢包在各个工序间周转的主要运输工具.天车调度须服务于工序调度，良好的天车调度是工序调度稳定进行的有力保证.同时，天车调度受制于工序调度且天车调度具有更高的时间精度要求，生产工序上分钟级别的扰动可能造成天车调度结果的改变.目前炼钢车间中，频繁的动态调度是天车调度的必然选择.

图 1给出了某钢厂钢水精炼跨天车调度环境的平面图.钢包的物流过程可由图中步骤①~④描述：钢包从转炉(工序1)盛接钢水，钢包车将钢包从转炉位运输至吊包位(步骤①)；天车将钢包从吊包位吊起，运输至某精炼(工序2)工位对应的落包位，并将钢包放置于对应的钢包车上(步骤②)；钢包车将钢包运输至精炼位处理(步骤③)；处理结束后运输至下一跨(步骤④).天车的运输任务(步骤②)即是将钢包从一个工序运输至下一工序.另外，由于双精炼工艺的存在(钢水需要在两个精炼工位处理)，钢包还可能从某精炼工位运输至另一精炼工位.

安装在同一轨道(X轴)的天车相互之间不能跨越且必须保持安全距离，称之为避碰约束，这是天车调度区别于其他机器调度的基本特征约束.同时，工位容量约束要求一个工位最多容纳一个钢包.最后，频繁的天车重调度必然面临不同的调度初始条件(不同的天车、任务、工位的初始状态)，从而对天车调度形成约束.

由于天车调度环境物理布局以及天车运行方式的不同，天车调度问题有不同的解决方案.目前国内外对天车调度的研究主要集中于集装箱港口岸桥和场堆龙门吊的调度.文献[1-2]对近年来该问题的研究进行了整体分析.岸桥在执行任务时，主体静止在任务X轴对应位置，沿着Y轴方向装卸货物.本文称这类天车为Y轴作业天车.Y轴作业天车将任务定义为在货物位置对货物的操作.受其影响，许多需要沿X轴将物品从A处运输到B处的天车调度问题，定义了同样的任务内涵，即将物品吊起和落下的操作分别定义为一个任务.这种任务定义方式能公式化推导避碰约束下任务的开始、结束时刻，适用于非仿真方法.但该定义增加了额外的求解约束，如吊起任务和落下任务需要同一辆天车连续执行.在该类任务定义下，Peterson等^[3]对某制造车间多天车调度问题建模，设计了天车最优路径方案，并利用启发式算法快速求得近优解.Cheng等^[4]对某仓库两天车调度问题建立了MIP模型，并用分支裁剪法求解.X轴作业天车任务的第二种定义将物品从A点到B点的整个运输过程作为一个任务.这种定义方式符合常规认知且能够利用简单的启发式规则快速求得近优解，但在避碰约束下推导任务开始时刻较为困难，一般采用仿真手段.王旭等^[5]、高小强等^[6]研究了制造车间天车调度问题.两者都设计了启发式天车分配和冲突消解规则，并利用仿真手段和改进的遗传算法进行求解；在时间目标函数方面，分别或共同考虑了最小化等待被运输时间，最小化天车对任务的响应时间和最短完工时间.Xie等^[7]对一个钢卷热处理工序的多天车调度问题建立了MIP模型并用一种启发式算法求解.求解过程中，为避免起重机的干扰，规定了天车的行为规范.实验结果表明提出的启发式方法可以生成高质量的解.Hirsch等^[8]设计了某制造车间两天车的运行方案，并利用蚁群算法求解了该调度问题.周炳海等^[9]提出一种全新的天车轨迹映射模型，结合传统差分进化方法，将库位分配规则和天车分配算法融合到调度算法的每一次迭代过程中以指导算法寻优.在自动化存储仓库的天车调度问题中，Kung等^[10]设计了一种启发式的天车运行方案以解决天车避碰，并提出一种基于动态规划的订单调度方法.李维刚等^[11]同样设计了任务分配规则，并采用改进的A^*算法计算天车路径，调度方案具有可靠性和高效性.

以上针对车间或仓库的天车调度研究，多以静态调度为主.其调度初始条件人为假设，无法解决动态条件下面临的任务、天车、工位各种初始状态对调度的影响；而动态调度的研究多采用实时调度策略，即每当一个任务到达时，根据任务分配规则将任务分配给某台天车.该策略具有较为严重的调度短视性.同时，以上车间天车调度研究忽略了工位容量，有可能产生不可行解.针对以上情况，本文利用滚动调度策略对炼钢车间天车调度问题进行了仿真研究.滚动调度实时对未来一小段时间内的任务进行预测，采用优化算法进行调度求解.又可以随着新任务的到来，不断进行重调度，进行快速响应.

本文首先针对任一重调度过程进行了建模.模型目标函数考虑了天车调度在时间节奏上需服从工序调度，同时考虑最小化天车工作量及其差异.约束条件在遵守天车避碰约束的同时，还考虑了工位容量约束和重调度初始条件对天车调度的约束.随后，提出了一种基于仿真的启发式方法对模型进行了求解，对图 1所示双天车调度进行了实例分析.

1 问题建模 1.1 问题描述

本文研究的多天车动态调度问题(简称DMCSP)中，天车的运输任务定义为将一个钢包从起点工位运输至终点工位.其包括3个过程：在起点工位吊起钢包；将钢包运输至终点工位；将钢包放置于终点工位.由于每次重调度中任务数量不多且天车数量有限，故重调度方式采用完全重调度，即对所有未完成任务和新到的任务重新分配天车.

假设某次重调度过程中任务数量为N.工位数量为M，工位首先以工序号排序，工序内工位从左向右排序.故图 1中工位1~4为转炉工位，5~11为精炼工位；工位在X轴上的位置已在图 1中标识.天车数量为K，天车从左向右排序.DMCSP中仅考虑天车沿X轴的移动(沿Y轴的移动忽略，沿高度方向的移动以固定的起吊时间和落包时间代替)，且移动速度固定.天车避让时的优先级与其当前任务在任务排序序列中的序列号一致；任务序列号越小，天车优先级越高.

DMCSP的每次重调度可描述为：对于N个任务，K台天车，在遵从天车移动行为约束、工位容量约束、初始条件约束的前提下，确定一个任务排序序列以及对应的天车分配序列作为问题解，以最小化完成N个任务时的时间惩罚值以及对天车工作量增加和差异的惩罚值.

DMCSP模型涉及的数学符号如下.

t，仿真系统时间, t=0，1，2，…;

t₀，当前重调度时刻;

N，任务数量;

K，天车数量;

M，工位数量;

δ，天车安全距离，天车中线之间的距离，δ=26 m;

Δ_{k, l}，任意两天车之间的最小的安全距离，k，l=1，2，…，K，k≠l; Δ_{k, l}=|k-l|δ;

v，天车移动速率，v=2/3 m/s;

O_m，t₀时刻工位m中的钢包数量，m=1，2，…，M；O_m=0，1;

L_m，工位m在X轴的位置，m=1，2，…，M;

a_i，b_i，任务i的起点、终点工位索引号，i=1，2，…，N，a_i，b_i=1，2，…，M;

r_i，任务i的释放时刻(到达吊包位的时刻)，i=1，2… N;

r′_i，任务i的计划释放时刻，从车间工序调度中获取；

s_i，e_i，任务i的开始、结束时刻，i=1，2，…，N；如果任务i重调度时未开始，s_i，e_i=0;

α_i，β_i，任务i中钢包起吊、落下所需时间，α_i=180 s，β_i=240 s;

C_i，任务i所分配天车的索引号，i=1，2，…，N，C_i=1，2，…，K;

R_i，任务i在任务序列中的排序序号(相当于任务i的优先级序号)，i=1，2，…，N;

R_{k, i}，在所有分配给天车k的任务中，任务i的排序序号，i=1，2，…，N；k=1，2，…，K;

I_{k, t，t}^c1时刻天车k任务的索引号，k=1，2, …, K；t=1，2, …; 如果0＜s_i≤t₀，I_{k, t0}^c1=1，2, …, N；否则，I_{k, t0}^c1=0，表示t₀时刻任务还未被天车k执行;

I_{k, j}^c2，分配给天车k的第j个任务的索引号，j=1，2, …, Nk^c；k=1，2, …, K；

P_{k, t}，天车k在t时刻的位置，k=1，2, …, K；t=1，2, …; 天车初始位置P_{k, 0}=(k-1)δ;

Z，多目标函数.

1.2 数学模型

天车调度应服务于工序调度以稳定工序生产节奏，表现为最小化.天车调度结果(记为对工序调度的影响(记为F_i)是非线性的^[12]，本文以指数形式量化该影响：

(1)

根据多次仿真实验，参数a赋值1.002.

第一个目标函数表述为

(2)

另外，目标函数还考虑了天车的工作量增量和不同天车历史总工作量之间的差异.天车历史总工作量，记为W_k，主要体现在其吊包、落包次数和负载、空载移动距离.本文将W_k量化为时间值：

(3)

其中：W_{k, t0}是重调度开始时天车k的工作量；D_{k, 1}，D_{k, 2}是当N个任务完成时，天车k空载、负载移动距离；λ₁(设λ₁=0.4)为权重系数.

目标函数Z₂表述为

(4)

其中λ₂(设λ₂=0.3)为权重系数.

最终，多目标函数表述为

(5)

综上，本文的DMCSP数学模型可表述为

(6)

服从于约束(7)~(13)：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

约束(7)~(9)由重调度时的不同初始条件产生.初始约束(7)和约束(8)要求若重调度时某任务正在被某天车执行，那么该任务仍分配给该天车，且必须作为该天车的第一个任务，否则不符合现实.约束(9)是工位容量约束，即若任务i的起点是任务j的终点，且任务i起点被占据，那么，任务i必须先执行，任务j才能执行.

约束(10)~(13)为天车移动行为约束.约束(10)要求天车的运行轨迹必须是连续的；约束(11)是避碰约束，要求相邻两台天车必须保持安全距离且不能相互跨越.约束(12)表明天车实际完成一个任务的时间，由于天车避让等原因，必然不小于该任务的理论完成时间.约束(13)规定一台天车在完成当前任务后，必须到达下一任务的起点且下一任务已经释放后，下一任务才能开始执行.约束(12)和约束(13)中Δ₁和Δ₂通过仿真获得.

2 实验方法 2.1 仿真过程总体方案

仿真平台分为两部分，如图 2所示.一部分为现实仿真模块，其模拟真实天车运行环境，同时管理任务，记录天车、任务、工位状态.另一部分为算法，当需要调度决策时，其首先从仿真模块获取当前仿真时刻天车、任务、工位的初始状态作为初始条件.然后算法模块生成有效解(调度方案)集合，并将每一个有效解以当前初始条件进行仿真运行.最终选取拥有最小目标函数值的解为最优解.该最优解将反馈给现实仿真模块，天车根据该解继续执行任务.如此，形成了一种滚动调度的动态调度模式.

在动态调度环境下，仿真平台需要对任务进行预测.由于任务产生与天车调度非同一层次问题，故仅在此简要描述.设定任务i的获知时刻为p_i，由任务i引发的重调度时刻为d_i.p_i，d_i和r_i对应车间某些关键事件发生节点.在p_i时刻，可以较为精确预测d_i和r_i，预测值分别记为d_i和r_i.同时，在p_i时刻仿真平台将模拟从上级工序调度中获取任务i的起点、终点，从而产生完整的任务信息.任务预测所用数据为炼钢车间历史生产数据，从数据中共获取30个运输任务，跨度约10 h，完整信息见表 1.仿真平台利用任务时间参数的到来，模拟对应事件的发生，从而释放任务.

2.2 天车运行方案

天车运行方案控制仿真过程中天车的运行行为.提出的天车运行方案适用于任意数量的天车，具有较好的拓展性.其包含一个主动运行方案和一个避让运行方案.

2.2.1 主动运行方案

天车在无干扰的情况下，完成一个任务需要经历5个步骤，本文称为天车的5个状态，如图 3所示.其中，细线表示天车处于空载状态(S_{k, t}=0，1)，粗线表示天车处于负载状态(S_{k, t}=2，3，4).其中，S_{k, t}=0表示任务i的d_i时刻未到达，或天车没有任务；S_{k, t}=1表示天车从当前位置移向任务i起点工位；S_{k, t}=2表示天车起包过程；S_{k, t}=3表示天车吊运钢包至任务i终点工位；S_{k, t}=4表示天车落包过程.

天车k在执行任务i时，其状态变更逻辑流程如图 4所示，图中T_c为天车当前状态的变更时刻.图 4给出了天车状态变更的判断逻辑，也给出了天车位置变更的函数.当天车k处于S_{k, t}=1或者3时，须向当前状态下的目标点(任务起点或终点)移动：

(14)

其中：L_dest是目标点所在位置；sign(x)是符号函数:

(15)

重调度时某低优先级天车l可能处于S_{l, t}=2或4，当前过程无法中断.若此时高优先级天车k向天车l移动，且|P_{k, t}-P_{l, t}|＜Δ_{k, l}时，天车位置更新为

(16)

另外，当拥有高优先级任务的天车k处于S_{k, t}=0时，规定其须避让其他天车，表述为P_{k, t}=h(k，P_{l, t}).

2.2.2 避让运行方案

低优先级天车在执行任务的过程中，为避让高优先级天车，可能需要经过多个中间过渡点，记为P_mid.以某两天车(低优先级天车l和高优先级天车k)为例，天车l在完成任务过程中最多需要经过1个P_mid, 可能的情况如图 5所示.图 5a中两天车任务区域不重叠，天车各自按其主动运行方案移动；图 5b中天车l须在S_{l, t}=1阶段移动到P_mid以避让天车k; 而图 5c中天车l须在S_{l, t}=3阶段移动到P_mid以避让天车k.故天车l的避让运行方案可描述为：天车l按主动运行方案移动→如果需要，在特定S_{l, t}下移动到P_mid→等待继续执行任务的条件判断→继续按主动运行方案完成任务剩余部分.当有n台天车优先性高于天车l时，天车l最多需要经过n个P_mid，该逻辑流程可由以上描述拓展得到.

由于P_mid的限制，低优先级天车会提前避让潜在冲突从而避免在现实中较为常见的无效折返跑.并且P_mid的限制也使得高优先级天车在S_{k, t}=0时即使避让低优先级天车，也不会导致其无效折返跑而增加额外工作量，更加符合现实天车运行行为.

2.3 启发式方法

每一个重调度的解包括一个任务排序序列和对应的天车分配序列.

记I_[i]表示任务序列中第i个任务的索引号.构建任务序列的方法如下：

1) 以r_i升序排列N个任务，构成第一个任务序列.以约束(7)~(9)检验和调整任务序列，得到第一个合法的任务序列.

2) 若两个相邻任务所在区域发生重叠，两任务的r_i相差5 min(经验值)且未违背约束(7)~(9)，则允许其交换顺序.任意合法的任务排序交换都生成新的任务序列.

对于每个任务序列，其所有天车分配序列构建如下：

1) 根据约束(7)，正在被执行的任务将继续分配给执行该任务的天车；

2) 其他任务按照穷举法分配天车.

对于以上构造的天车分配序列，不符合下列规则的序列将被排除：

1) 连续3个任务不能分配给同一天车；

2) 如果任务区域不重叠，则天车不可交叉分配，如图 5a所示.这符合已被证明存在最优解的单向调度策略^[13]，即若，则；或者，则.

3 实验结果及分析

仿真平台利用C#语言在Microsoft Visual Studio 2013软件上编写.计算机安装Win 10系统，8 GB内存，CPU型号为Intel(R) Core(TM) i3-6100 @ 3.7 GHz.

仿真实验中天车数量根据现场实际设定为2台，任务见表 1.动态调度的结果展示于图 6a，其为天车在各个工位间执行任务的轨迹.轨迹图可以得到任务分配方案和任务开始、结束时刻.下部轨迹属于天车1，而上部轨迹属于天车2.两条轨迹中，粗线部分天车处于负载状态(S_{k, t}>1)而细线部分处于空载状态(S_{k, t}≤1).图中两天车轨迹不相交，满足避碰约束.天车到达任务起点时，大多数任务并未释放，不会造成额外的任务延迟.表 1中30个任务的调度过程计算耗时为0.22 s，每个重调度过程则更少，完全满足实际调度的实时性要求.炼钢车间天车任务是随着主工序的生产节奏而产生，故不会导致批量任务同时释放.在滚动调度策略下，每次重调度的任务规模不超过5个.总的任务规模增大，仅会导致重调度的次数和整个仿真过程耗时增加，而对每次重调度的实时性影响较小.

模型目标函数使得本文天车调度方案具有维护生产调度稳定性和平衡天车工作量的作用.例如，人为调换任务2和任务3的计划释放时刻以模拟任务3因某种原因导致落后于工序调度计划，此时任务3优先级将提升而高于任务2，执行结果如图 6b所示.又如，设置天车2在t=0时的初始工作量为50 min，则在后续调度中，任务将趋向于分配给天车2以平衡两车的工作量，如图 6c所示.

表 2对比了滚动调度策略与实时调度策略下的天车调度结果，滚动调度策略下分别采用了提出的启发式方法和枚举法进行了对比.枚举法因能遍历所有解，其取得的解是局部最优解.同时，在实时调度策略下对比了提出的启发式方法(此时相当于一种贪婪算法)和规则调度(向左任务由左边天车执行，向右任务由右边天车执行).

从各种指标看，在滚动调度策略下，提出的启发式算法相对于枚举法，其惩罚值增加了3.7 %.即提出的启发式算法优化性能达到枚举法的96.3 %，说明提出的启发式方法能够获得良好的近优解.同样的启发式方法下，滚动调度策略总惩罚比实时调度策略下总惩罚降低了17.8 %，表明本文采用的滚动调度策略具有一定前瞻性，其调度性能优于实时调度策略.而在滚动调度策略下，提出的启发式方法相较于规则调度方法，惩罚值下降了10.5 %.现场一般采用实时调度策略下的规则调度，提出的滚动调度策略下的启发式方法相对于现场采用的实时规则调度，调度优化性能提高26.4 %.偏离度的存在是由于调度决策时任务时间信息采用了预测值，而实时调度发生于任务真实释放时刻，从而导致滚动调度下偏离度大于0而实时调度策略下偏离度等于0.滚动调度仿真实验中d_i和r_i较为正常，其偏离度相对于每个任务的平均值仅为169/30=5.6 s，现实情况下该平均值可能会较大.对于任务执行效率E，由于天车需要从上一个任务终点移动到下一个任务起点，且由于避碰约束，天车执行任务的效率不能达到100 %.现场一般要求天车利用率Q小于70 %，从实验结果分析，两种策略均满足要求，且实时调度策略表现更优.目标函数中，天车空载移动折算的工作量较小，本文天车调度方案更加注重通过较多的空载移动以均衡工作量，从而使得在利用率指标上处于较小劣势.

4 结论

1) 本文提出的炼钢车间天车动态仿真调度方案能够促进工序调度的稳定，减少和均衡天车工作量.提出的启发式算法的实时性保证了本方案的可行性，天车利用率满足现场要求.

2) 滚动调度策略下，提出的启发式方法所得解的优化性能最高能达到最优解的96.3 %.

3) 提出的滚动调度策略下的启发式方法相比于现场采用的实时规则调度方法，调度优化性能提高26.4 %.