多阶段人机协同的炼钢—连铸调度方法

赵 宁，李 亮，杜彦华

（北京科技大学 机械工程学院，北京 100083）

0 引言

炼钢—连铸是将铁水等原料通过炼钢转化为液态钢水，再通过精炼和连铸转化为固态钢坯的生产过程。该过程的加工对象是炼钢后放在钢包中的钢水，因此炼钢—连铸生产调度一般以炼钢炉中的钢水为调度对象，称为炉次。炼钢—连铸生产调度计划是在批量计划的基础上，以炉次为最小计划单位，在满足温度、连铸等约束的前提下，追求综合评价函数，如等待时间最小、提前／拖期费用和总流程时间最少等最佳情况下的一类排序问题［1］。相对其他调度问题，炼钢—连铸调度存在约束多、节拍紧的特点，被认为是最难的流水车间调度问题之一［2］。炼钢—连铸调度问题具有很高的研究价值与实用价值，也有很多优化目标，其中最小化总流程时间（Makespan）是相对最重要的优化目标，并吸引着众多研究者参与其中。

早期关于炼钢—连铸调度的研究侧重于机器调度，即通过计算机和算法快速寻找最优或满意的调度解。因此，机器调度又可分为最优和近优两大类，最优方法包括整数规划法［3］和拉格朗日算法［4］等，它们大都是以遍历问题的所有可行解为手段，适合规模小、约束条件少的调度计划编制问题；近优方法包括蜂群算法［5］、遗传算法［6］、粒子群算法［7］和邻域搜索方法［8］等，这些近优方法得到的结果虽然不一定最优，但是计算的效率高，对解决大规模调度问题很有效。

尽管机器调度已经取得了很多研究成果［3-8］，但在实际的炼钢—连铸生产调度时，仍存在很多需要依靠经验的情形，具体表现在：

（1）炼钢调度存在一些经验规则，如尽量将相似钢种安排在同一设备、尽量将钢水安排在以往质量较稳定的设备、钢水等待时间尽量少、尽量考虑设备维护的影响等。这些规则并非在每次调度时都要遵守，在实际生产时仍要依据不同的钢种、不同的生产状况由调度员凭经验掌握。

（2）实际生产的状况千变万化，目前的调度模型难以涵盖生产现场随时可能提出的各种调度需求，当机器调度难以满足需求时，仍要依赖调度员的经验调度。

因此很多文献都指出，在目前的炼钢—连铸调度中，调度员的经验仍不可替代［9-12］。很多学者在炼钢—连铸调度领域开展人机协同调度的研究，取得了一些成果［9-14］，并已经在一些钢厂获得实际应用，产生了经济效益。但这些方法仍存在如下不足：

（1）人工调度和机器调度分工明确、各自为政，调度员可以干预调度结果，但无法涉足优化过程，调度员难以参与各种优化算法的运算过程，调度算法也难以与调度员的经验相结合。

（2）这些方法都是由机器调度产生一个初始解，再由调度员凭借经验对调度解加以调整。炼钢—连铸调度存在紧前约束、设备资源约束、连铸约束和运输时间约束等调度约束，在调整过程中调度员不得不投入大量精力来满足这些调度约束，影响人机协同的调度效率。

本文针对以上问题提出一种多阶段人机协同调度方法（Multi-Stage Man Machine Cooperated scheduling method，MSMMC），该方法提供了调度员参与优化过程的接口，可以将机器调度的特点与调度员的经验相结合，通过人机协同的方式实现调度解的调整和优化。与已有方法相比，本文所提方法具有以下优势：

（1）使调度员更容易理解机器调度过程并参与其中，从而更好地发挥调度经验的优势。

（2）可训练并增强人的调度能力，当出现机器调度难以处理的情形时，人工调度会发挥更多优势。

2 多阶段调度优化

本文的主要目标是缩短整个调度计划的完工时间Makespan。建立调度数学模型如下：

其中：i为炉次序号；Ω 为没有浇铸结束的炉次的集合，i∈Ω，|Ω|为炉次总数；n为浇次号，N 为浇次数，n=1，2，…，N；Ωn为第n 浇次中没有浇铸结束的炉次集合，Ω1∩Ω2∩… ∩ΩN=Ø，且Ω1∪Ω2∪… ∪ΩN=Ω；Si为炉次i的工序总数，由于精炼总数的不同，所有炉次计划的工序总数不完全相同；j为工序序号，1≤j≤Si；Θ′i为炉次i的所有工序集合；Θi为炉次i没有开始生产的工序集合；M 为机器总台数；k为机器序号，1≤k≤M；kij为炉次i工序j所在的机器序号；stijk为 炉次i工序j 在机器k上的加工开始时间；Xijk为炉次i工序j 在机器k 上调度优化后的加工开始时间，选为模型的决策变量；ptijk为炉次i在工序j的机器k 上的工艺加工时间；tmax为钢包在两工序间的最大等待时间；tmin为钢包在两工序间的最小等待时间；utkk′为炉次从机器k到机器k′的运输时间；SI（i，j，k）为炉次i在工序j的机器k上的紧后炉次。

式（1）为目标函数，即调度计划的完工时间最短；式（2）表示在同一台设备上相邻炉次间要等到前一炉次加工完后才可进行下一炉次的加工；式（3）表示同一炉次相邻工序间要等到前一工序加工完后才可进行下一工序的加工；式（4）表示同一炉次的相邻工序在进行设备间运输的过程中，运输时间必须在一定范围内，否则会导致钢水温度不满足温度约束；式（5）表示同属一个浇次的炉次在连铸机上加工时要保证连续生产约束，否则会导致断浇事故；式（6）表示每炉次的开始时间应大于等于0。

以上模型表达了本文所考虑的炼钢—连铸调度的优化目标和约束条件。此处假定所有炉次可在任一并行机上加工，则调度的内容是确定所有炉次的加工设备、先后次序和开始时间，在满足所有约束条件的基础上使总加工周期最短。以上模型虽然表达了炼钢—连铸调度的约束和目标，但是无法描述前文所述的依靠调度经验的情形。这些情形较难纳入调度模型中考虑，在实际生产中一般都需调度员凭借经验手动调整。

为了使机器调度与手工调度能够优势互补，有必要设计一种便于调度员理解和参与的调度算法，使调度经验能够融入机器调度过程中。因此，本文设计了MSMMC，该方法借鉴经典调度中的邻域搜索和关键路径方法。其基本思路是先产生一个初始调度解，再根据该调度解的关键路径对该调度解进行邻域搜索，调度员可参与机器搜索过程并在搜索过程中添加约束，通过人机协同调度直至找到满意的调度解。MSMMC 的优化调度过程具体分为如下几个阶段：

（1）第一阶段 以手动调度或其他自动调度方式生成初始调度解。

（2）第二阶段 调度员判断调度解是否满足要求，如果不满意则可凭借经验手动调整工序所在的炼钢、精炼设备以及工序加工顺序，系统采用贪心和反贪心算法对人工调整解进行自动修正，在满足各项约束的基础上尽量缩短生产周期。

（3）第三阶段 采用极值法对关键路径进行邻域搜索，并采用约束联动方法获得满足约束的优化解。调度员评价优化解的生产周期是否满意，如果满意则调度结束；否则可再次对优化解进行人工调整，然后重复该阶段直至满意。MSMMC 调度过程如图1所示。

在图1所示的MSMMC优化过程中，人工调整是第二阶段和第三阶段的核心。人工调整的方法有调整工序、加工顺序、调整工序设备、调整工序开始时间等。此处采取的是基于关键路径的邻域搜索方法，其搜索过程相对更容易被调度员理解，而调度员在人工调整过程中只需考虑需要凭借调度经验解决的问题，调度模型中的约束则由机器加以保障。当人工调度结束后，系统再不断以调度员的调整解为基础进行新一轮邻域优化，直至获得满意的调度解。与以往的方法相比，多阶段人机优化调度方法在优化过程上提供了多个调度员的参与点，从而能将调度经验更好地融入优化过程，实现机器和调度经验的优势互补。特别地，如果不需要调度经验干预，则可在多阶段人机优化调度过程中跳过人工调整，进行下一轮邻域搜索，从而起到快速寻优的效果。

3 关键技术

下面依次对多阶段人机协同调度过程中存在的关键技术进行说明。

3.1 贪心算法与反贪心算法

贪心算法是根据给定的调度方案，计算每道工序的开始加工时间，通过缩短同台设备上工序与工序间的间隔时间，使工序的可开始加工时间变得最早，通过该策略对调度解进行修正，使调度解满足约束并变得更为紧凑。以炉次i的工序j 为例，在计算最早开始加工时间时，需要按照以下公式进行计算：

式中：i′和j′分别表示与炉次i的工序j 安排在同一设备上相邻的前序炉次，表示炉次i 的第j 道工序的最早开始加工时间，表示炉次i 的第j 道工序的完工时间。式（7）表达了最早开始时间等于该炉次上一工序的结束时间加最短运输时间与同一设备上一工序结束时间的最大值，式（8）表示最早结束时间可由最早开始时间与加工时间之和求得。

算法1 贪心算法。

步骤1 按式（7）和式（8）计算炉次i工序j 的开始时间和结束时间。

步骤2 j=j+1，按式（7）和式（8）计算下一工序的开始时间和结束时间，直至遍历炉次i的所有工序。

步骤3 针对与炉次i的工序j 同一设备的下一工序，按式（7）和式（8）计算开始时间和结束时间，直至遍历炉次i的工序j 同设备的所有后续工序。

可见，贪心算法是在保证紧前约束和设备资源约束的基础上获得最早可开始时间，并将每一工序按其最早可开始时间调度，从而使Makespan 尽可能短。同理，反贪心算法则是由最后一道工序的开始时间推算，在保证紧前约束和设备资源约束的基础上依次获得以上每道工序的最晚可开始时间，并将每一工序按其最晚可开始时间进行调度，反贪心算法与贪心算法的计算过程则完全相反，这里不再赘述。贪心算法忽视了连铸约束和运输时间约束，追求最早可开始时间，可用于Makespan 的优化；而反贪心算法则用于确保连铸约束和运输时间约束，可用于优化后的人工调整。

3.2 基于关键路径的邻域搜索

关键路径是指炼钢—连铸调度计划中对整个调度计划影响最大的加工路径，通过对关键路径进行领域搜索，可以有效提高搜索效率。根据已知的调度方案选择出最后完工的炉次工序，利用逆推法决定关键路径，通过交换关键块中的工序次序和更换连铸设备实现邻域搜索。

逆推法首先将最后完工工序设为关键工序，再将关键工序所在设备的前驱工序和同一炉次的前驱工序进行比较，取结束时间较大的前驱工序作为下一个关键工序，依次类推，直至找到开始时间最早的工序。按照这一方法可以得到一条对整个调度计划影响较大的关键路径。在逆推过程中，如果遇到设备前驱工序的结束时间与炉次前驱工序的结束时间相等，则取炉次前驱工序作为下一个关键工序，这是因为炉次前驱工序约束等级高于设备约束等级。

本文将邻域分为邻域由关键路径决定和邻域由铸机选择决定两部分。其中关键路径邻域搜索的基本思路是：根据逆推法可获得任一调度方案的关键路径，更换关键路径中的工序顺序、获得新的调度方案，新调度方案即为旧调度方案的邻域。在得到的关键路径中必定包括了转炉设备的工序块、精炼设备的工序块和连铸机设备的工序块，在关键路径中放置于转炉和精炼设备上并受设备资源约束限制的连续工序称为关键块。关键块中的工序两两置换后得到的新调度解称为原调度解的邻域。如果关键块中只有一道关键工序，则不需要交换，如果关键块中有两道以上关键工序，则依次进行两两交换。在所有关键块都交换完毕后得到的邻域解中取最优解，如果最优邻域解优于原调度解，则保留最优邻域解并开始新一轮邻域交换，反之则搜索完毕。

铸机选择邻域搜索是本文定义的另一邻域搜索方法，仅将铸机选择作为搜索范畴主要基于如下考虑：

（1）铸机是炼钢过程的最后一台设备，因此铸机选择对生产周期有直接影响。

（2）如果将所有设备的选择都作为邻域搜索的范畴，则会极大地增加搜索空间，影响搜索速度，导致调度人员等待时间过长，影响人机协同效果。

本文仅将连铸设备的选择纳入邻域搜索，炼钢、精炼设备的选择通过人工调整完成。当然，调度员也可对机器选择的铸机进行手动调整，但此时最终调度方案的生产周期可能会比机器搜索方案的生产周期更长。

铸机选择邻域搜索的基本思路是采用极值优化（Extremal Optimization，EO）方法，该方法是受复杂系统自组织临界进化模型的启发形成的一种启发式智能算法［16］。EO 方法的基本出发点是将问题分解成低耦合度的局部变量，考查各变量对解的贡献，并将其量化为适应度。对适应度最低的变量取值进行修改，使其适应度提高，从而提高解的质量。

算法2 EO 算法。

步骤1 找出调度方案中最晚完工的机器，令其为M1。

步骤2 找到M1 的末道工序，将其定义为当前工序A。

步骤3 在A 的可加工机器集合上找到最早结束加工的机器，令其为M2。根据不同情形，将工序A 变换到M2设备上，变换时依据式（2）和式（3）计算变换工序的开始时间和结束时间。

（1）若设备M2的末道工序B 的结束时间小于A 的开始加工时间，则直接将设备M1上的末道工序A 排在B的后面。如图2所示。

（2）若M2上的末道工序B 的结束时间大于等于A 的开始时间，则从设备M2的末道工序开始向前查找加工时间小于A 的加工时间的工序，然后进行交换。如图3所示。

（3）如果B的加工时间小于A 的加工时间，则把A 与B进行交换。如果B 的加工时间大于等于A 的加工时间，则在设备M2上从B 开始向前寻找加工时间小于A 的工序C，然后进行交换。如图4所示。

步骤4 判断变换后的新方案，若仍存在上述三种情形，则转步骤3，否则算法结束。

在以上两种邻域搜索方法的基础上，对任一初始解，依次结合关键路径法和EO 算法进行邻域搜索，每次都会得到一个完工时间更小的新调度方案。新调度方案又会产生新的关键路径，可进一步通过关键路径和铸机选择搜索更优的新调度方案。如此循环，当完工时间不再缩小时搜索结束。值得一提的是，如果调度员不满意，则可在结果的基础上调整炼钢和精炼设备的选择，调整之后的邻域搜索可望获得更好的结果。

3.3 基于约束的联动调整

在通过关键路径搜索得到优化解的基础上，考虑约束模型中的紧前约束、设备资源约束、连铸约束和运输时间约束，在保证上述约束的基础上实现调度解的联动调整，从而减轻调度员的负担。具体的联动调整步骤如下：

算法3 约束联动调整算法。

步骤1 针对调度员调整后的结果，按加工顺序遍历所有炉次的所有工序。

步骤2 对遍历工序按照式（2）和式（3）进行紧前和设备资源约束判定，对有约束冲突的工序按贪心算法进行调整，以满足约束。

步骤3 针对上述调整结果，按反向加工顺序遍历所有炉次的所有工序。

步骤4 对遍历工序按照式（4）进行连铸约束判定，对不满足连铸约束的按反贪心算法调整铸机工序。

步骤5 对遍历工序按照式（5）进行运输时间约束判定，对不满足约束的按运输时间调整算法进行调整。

其中步骤5的运输时间调整算法如下：

算法4 运输时间调整算法。

步骤1 先进行精炼炉到连铸机的运输时间调整，对精炼炉上的工序，从每台精炼设备上的末道工序开始，依次进行设备前驱工序前推。

步骤2 根据精炼炉上工序的结束时间和该工序的后继工序开始时间进行差值计算，设差值为ΔT。如果ΔT ＞tmax，则进行精炼炉上该工序的后移，后移值为ΔT-tmin。

步骤3 调整完精炼炉后，利用相同的原理调整转炉到精炼炉的运输时间。按连铸机工序顺序前移，转步骤1，直至遍历所有铸机工序。

以图5为例说明算法4的思路。从图5可以看出：1-12-2到1-12-3的运输辅助时间ΔT ＞tmin，因此1-12-2号工序需要进行调整。将1-12-2道工序的开始时间加上ΔT-tmin，使得该工序的结束时间与后续工序开始时间的时间差为tmin，从而保证了约束模型中运输时间的限制和计划的可行性。

4 实例分析及性能测试

基于上述内容开发了炼钢—连铸调度系统，并进行了实例分析和性能测试。

4.1 实例分析

以文献［15］中机器调度的最终优化结果对比说明本文方法。在该实例中的生产工艺路线为转炉、精炼和连铸，使用转炉2台、精炼炉3台、连铸机3台，针对一个浇次的18炉钢进行生产计划调度。在调度系统中建立文献［15］最终的优化结果，如图6所示。

以该结果为初始解，利用贪心算法进行方案的初步调度优化，得到的结果如图7所示。

可以看出，贪心算法计算后的方案在完工时间上虽然较之前的方案没有改进，但大幅提前了炼钢和精炼阶段工序的开始时间，在此基础上可进一步通过关键路径法优化。图7中的关键路径为1-1-1，1-3-1，1-3-2，1-3-3，1-6-3，1-9-3，1-12-3，1-15-3，1-18-3，如图8所示。

对图8中关键路径所形成的邻域进行搜索并进行约束联动调整，优化结果与图8一致，调度员去除等待时间约束的优化结果如图9所示。

由图9可见，优化后的生产周期比初始解减少了15min，但造成第2，4，6，8，10，14等多个炉次的转炉结束时间与精炼开始时间的差距过大，虽然满足了运输时间约束，但整体等待时间过大会造成温度损耗并给生产带来隐患。因此，图9 结果与图6结果相比，虽然生产周期更优，但整体衡量未必更好，这从另一方面也说明了文献［15］的机器调度结果在2台转炉情况下已较优，而本文方法可达到文献［15］的同等效果。

假设此时调度条件发生变化，生产现场要求将17，18炉次转做方坯，同时要求生产周期尽量缩短，调度员可凭借调度经验（考虑钢种类似、等待时间较多的炉次）在图9的基础上手动调整3，6，9，12，15，17，18等工序的加工设备，利用贪心算法修正后的结果如图10所示。

由图10可见，人工调整后使用了转炉3和方坯铸机1，生产周期比初始方案缩短了75 min。在人工调整的基础上进一步利用邻域搜索优化，再用约束联动方法修补约束后的调度结果，如图11所示。

图11所示结果的生产周期比初始方案提前90 min，同时各炉次间满足等待时间约束。如果该方案仍不满足要求或生产现场提出新的调度要求，则可再次利用人工调整，结合机器调度算法进行新一轮优化，直到满意为止。

4.2 性能测试

在人机结合调度过程中，机器算法的运算效率对人机结合调度的效果有较大影响。为了检验本文算法的响应速度，针对炉数在10炉～30 炉的调度计划随机生成不同的初始解，对初始解进行算法优化并对算法效率进行测试，测试结果如图12所示。

从图12可以看出，算法运算时间会随炉次的增加而增加，但在30炉时最长也不超过10s，在人能够承受的等待时间范围内。此外，由第15 炉和26炉的对应时间可知，算法运算时间并不平滑，这一现象可能是由不同的初始解造成的。对于是否会有个别初始解造成运算时间非常长的情况，以18炉钢为例，随机形成30个不同的初始调度方案，实验结果如图13所示。结果显示，18炉钢的算法执行时间平均为2s，最长时间不超过8s，整体仍处于可承受范围之内。因此，算法具有较好的计算效率，在人机协同过程中不会导致调度员等待较长时间。

5 结束语

本文针对炼钢—连铸调度问题提出一种多阶段人机协同调度方法。该方法以最小完工时间为目标，采用最早完工贪心算法进行初优化，再结合关键路径和邻域搜索方法进行优化，调度员凭借经验可干预优化过程，从而更快地获得满意调度解。通过实例表明，本文提出的多阶段人机协同调度方法可以充分发挥调度人员的经验，能够获得更好的调度解。算法性能测试表明，本文提出的机器调度算法具有较好的计算性能，能够配合调度员快速有效地对调度方案进行优化。

目前本文工作还停留在炼钢—连铸的静态调度阶段，而动态调度是更能发挥人机协同优势的调度领域。因此，开展人机协同动态调度的研究将是未来的研究方向。

［1］WANG Bailin，LI Tieke，ZHANG Chunsheng，et al.Dynamic CSP based scheduling algorithm for steelmaking &continuous casting with conticaster breakdown［J］.Computer Integrated Manufacturing Systems，2011，17（10）：2185-2193（in Chinese）.［王柏琳，李铁克，张春生，等.基于动态约束满足的考虑连铸机故障的炼钢连铸调度算法［J］.计算机集成制造系统，2011，17（10）：2185-2193.］

［2］PACCIARELLI D，PRANZO M.Production scheduling in a steelmaking-continuous casting plant［J］.Computers and Chemical Engineering，2004，18（12）：2823-2835.

［3］NAPHADE K S，WU S D，STORER R H，et al.Melt seheduling to trade off material waste and shipping Performance［J］.Operations Research，2001，49（5）：629-645.

［4］XUAN Hua.Three-stage HFS scheduling problem with serial batching machines［J］.Computer Integrated Manufacturing Systems，2012，18（5）：1006-1010（in Chinese）.［轩 华.含串行批处理机的三阶段混合流水车间调度问题［J］.计算机集成制造系统，2012，18（5）：1006-1010.］

［5］PAN Quanke，WANG Ling，MAO Kun.An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process［J］.IEEE Transactions on Automation Science and Engineering，2013，10（2）：307-322.

［6］SANTOS C A，SPIM J A，GARCIA A.Mathematical modeling and optimization strategies（genetic algorithm and knowledge base）applied to the continuous casting of steel［J］.Engineering Applications of artificial Intelligence，2003，16（6）：511-527.

［7］TANG Lixin，WANG Xianpeng.An improved particle swarm optimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry［J］.IEEE Transactions on Control Systems Technology，2010，18（6）：1303-1314.

［8］DONG Hongyu，HUANG Min.Improved varible neighborhood search for integrated tundish planning in steelmaking process［J］.International Journal of Production Research，2012，50（20）：5747-5761.

［9］CHEN Kai，ZHENG Zhong，GAO Xiaoqiang.Computer-aided planning and scheduling system for steelmaking-continuous casting［J］.Journal of Iron and Steel Research International，2010，17（2）：29-34.

［10］YU Shengping，CHEN Wenming，PANG Xinfu，et al.Simulation system of dynamic scheduling of steelmaking &continuous casting based on graphic edit platform［J］.Journal of System Simulation，2009，21（16）：5145-5149（in Chinese）.［俞胜平，陈文明，庞新富，等.基于图形化编辑平台的炼钢连铸动态调度仿真系统［J］.系统仿真学报，2009，21（16）：5145-5149.］

［11］ZHAO Ning，DU Yanhua，DONG Shaohua.Dynamic simulation scheduling oriented to temperature constraints and continuous production constraints［J］.Computer Integrated Manufacturing Systems，2013，19（1）：97-105（in Chinese）.［赵 宁，杜彦华，董绍华.温度和连续生产约束下的动态仿真调度［J］.计算机集成制造系统，2013，19（1）：97-105.］

［12］WANG Chao，LI Tieke，ZHANG Wenxue.Dynamic scheduling for steelmaking &continuous casting based on humancomputer interaction［J］.Application Research of Computers，2011，28（4）：1378-1381（in Chinese）.［王 超，李铁克，张文学.基于人机交互的炼钢连铸动态调度［J］.计算机应用研究，2011，28（4）：1378-1381.］

［13］WANG Xiuying，CHAI Tianyou，ZHENG Binglin.Intelligent scheduling software &its application in steelmaking &continuous casting［J］.Computer Integrated Manufacturing Systems，2006，12（8）：1220-1226（in Chinese）.［王秀英，柴天佑，郑秉霖.炼钢—连铸智能调度软件的开发及应用［J］.计算机集成制造系统，2006，12（8）：1220-1226.］

［14］ZHAO Ning，DING Wenying，DONG Shaohua，et al.Dynamic schedule of steel making-continuous casting based on group adjustment orienting restrict［J］.Systems Engineering—Theory &Practice，2011，31（11）：2176-2184（in Chinese）.［赵 宁，丁文英，董绍华，等.基于约束联动的炼钢—连铸动态调度［J］.系统工程理论与实践，2011，31（11）：2176-2184.］

［15］YU Shengping，PANG Xinfu，CHAI Tianyou，et al.Production mode and optimization scheduling model for steelmaking and continuous casting［J］.Systems Engineering—Theory &Practice，2011，31（11）：2166-2176（in Chinese）.［俞胜平，庞新富，柴天佑，等.炼钢连铸生产模式及优化调度模型［J］.系统工程理论与实践，2011，31（11）：2166-2176.］