基于时间窗的炼钢-精炼-连铸生产过程的调度方法及装置

摘要

本发明提供了一种基于时间窗的炼钢-精炼-连铸生产过程的调度方法，该调度方法基于初步可行调度计划，生成时间约束网络；针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d

说明书

技术领域

本发明涉及炼钢-精炼-连铸生产过程的调度方法和调度装置，更为具体地，涉及基于时间窗的炼钢-精炼-连铸生产过程的调度方法和调度装置。

背景技术

在目前的钢铁生产过程中，钢铁企业生产部门通常将炼钢-精炼-连铸三个工序作为一个整体来进行生产计划编制，形成生产批量计划。然后，将所形成的生产批量计划下达给各生产厂执行，例如，下达给进行炼钢-精炼-连铸生产过程的炼钢厂。在下达给炼钢厂的生产批量计划中，指定了在连铸工序上需要加工的各个浇次和板坯交货时间，并要求炼钢厂按照连铸板坯交货时间要求生产出合格板坯。在接收到生产批量计划后，炼钢厂需要根据生产批量计划来编制炼钢-精炼-连铸生产过程的生产调度计划，以实现在工艺约束条件下最大程度地满足连铸板坯的交货时间要求的同时，使得完成全部工件的时间最短。

炼钢-精炼-连铸生产过程是一种高温、连续且伴随着物理及化学变化的复杂生产过程，其通常涉及多个炉次、多个工序、多个设备、多个阶段以及多个板坯。

这里要说明的是，术语“炉次”指的是炼钢-精炼生产过程的加工单位，根据具体生产厂不同，每个炉次可包含100-300t钢水。在本文中，用符号J₁，J₂，…，J_n表示n个炉次。

术语“工序”指的是每炉钢水要顺序经过炼钢、精炼方式1、...、精炼方式L、连铸等多种方式的加工，每次加工称作一个工序。在本文中，用符号O_i1，O_i2，…，O_im表示炉次i的第1到第m个工序。

术语“阶段”指的是炉次经过的加工方式。在本文中，用符号S₁，S₂，…，S_m表示m个生产阶段。

术语“板坯”指的是每个炉次的钢水经过连铸生产阶段后被浇铸成的板坯，每块板坯的重量通常为10几吨到几十吨。在本文中，用P₁，P₂，...，P_N表示N块板坯。

图1示出了现有的炼钢-精炼-连铸生产过程示意图。

如图1所示，在现有炼钢-精炼-连铸生产过程中，根据现有的调度方法，炉次J₁，J₂，...，J_n依序通过炼钢设备1，2，...，|S₁|、精炼设备1，2，...，|S₂|和连铸设备1，2，...，|S₃|，然后形成板坯P₁，P₂，...，P_N。

在现有调度方法中，通常是应用启发式或精确算法来确定各工序的加工设备并指定各工序的开始时刻，即指定各工序的开始时间点。

然而，由于炼钢-精炼-连铸生产过程是一个高温且连续的生产过程，并伴随有复杂的物理及化学变化，因此，在炼钢-精炼-连铸生产过程中，常常存在许多不可预测的影响因素，从而导致炼钢-精炼-连铸生产过程很容易偏离生产调度计划。从上可知，在现有调度方法中只给出了各工序的开始时刻，并没有给出不影响生产调度计划的各工序的最晚开始时间。也就是说，根据现有调度方法所编制的生产调度计划是一种定点计划。因此，在生产过程偏离生产调度计划时，生产管理人员不能够根据所编制的生产调度计划判断实际生产过程偏离生产调度计划的程度，以及该种偏离是否会对炼钢-精炼-连铸生产过程产生影响，从而不能在偏离程度对生产过程产生不良影响时及时对生产调度计划进行调整。

因此，需要一种新的炼钢-精炼-连铸生产过程的调度方法，其能够指定各工序在各加工设备上的[最早开始，最晚开始]时间窗口，从而使得生产管理人员在生产过程中出现意外因素时及时对调度计划进行调整。

发明内容

鉴于上述问题，提供了一种基于时间窗的炼钢-精炼-连铸生产过程的调度方法和调度装置，该调度方法和装置基于初步可行调度计划，生成时间约束网络；针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d_i0以及节点0与各节点i之间的最短时间距离d_0i，以获得各节点i的时间窗[-d_i0，d_0i]；并根据所获得的各节点i的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划。利用该调度方法，生产管理人员不仅能够知道各工序的最早开始时间，同时也知道在不影响计划目标的前提下各工序的最晚开始时间，从而可以在生产过程中出现意外因素时及时对调度计划进行调整。

根据本发明的一个方面，提供了一种基于时间窗的炼钢-精炼-连铸生产过程调度方法，所述方法包括：

基于初步可行调度计划，生成时间约束网络，其中所述初步可行调度计划中的各工序采用所述时间约束网络的两个节点表示该工序的开始和结束，所述时间约束网络中的节点0表示所述初步可行调度计划的开始；

针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d_i0以及节点0与各节点i之间的最短时间距离d_0i，以获得各节点的时间窗[-d_i0，d_0i]；以及

根据所获得的各节点i的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划。

根据本发明的另一方面，提供了一种基于时间窗的炼钢-精炼-连铸生产过程调度装置，所述装置包括：

时间约束网络生成单元，用于基于初步可行调度计划，生成时间约束网络，其中所述初步可行调度计划中的各工序采用所述时间约束网络的两个节点表示该工序的开始和结束，所述时间约束网络中的节点0表示所述初步可行调度计划的开始；

计算单元，用于针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d_i0以及节点0与各节点i之间的最短时间距离d_0i，以获得各节点的时间窗[-d_i0，d_0i]；以及

生产调度计划形成单元，用于根据所获得的各节点i的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划。

通过参考以下结合附图的说明及权利要求书的内容，并且随着对本发明的更全面理解，本发明的其他目的及结果将更加明白及易于理解。

附图说明

以下将结合附图和具体实施例对本发明进行详细描述，其中：

图1示出了现有的炼钢-精炼-连铸生产过程示意图；

图2示出了根据本发明的基于时间窗的炼钢-精炼-连铸生产过程调度方法的流程图；

图3示出了一个示例炼钢-精炼-连铸生产过程的时间约束网络的具体实例，所述示例炼钢-精炼-连铸生产过程包括6个炉次3个生产阶段，每个生产阶段设置有3个生产设备；

图4示出了时间区间约束的节点间的有向弧表示的实例的示意图；

图5示出了根据本发明的基于时间窗的炼钢-精炼-连铸生产过程调度装置的方框图。

在所有附图中相同的标号指示相似或相应的特征或功能。

具体实施方式

下面结合附图对本发明作进一步的说明。

图2示出了根据本发明的基于时间窗的炼钢-精炼-连铸生产过程调度方法的流程图。图3示出了一个示例炼钢-精炼-连铸生产过程的时间约束网络的具体实例，所述示例炼钢-精炼-连铸生产过程包括6个炉次3个生产阶段，每个生产阶段设置3个生产设备。图3中的时间单位为分钟，完成全部生产任务的目标时间假设为137分钟。很显然，完成任务的目标时间还可以为其它合适时间段。

如图2所示，在步骤S210，基于初步可行调度计划，生成时间约束网络，其中所述初步可行调度计划中的各工序采用所述时间约束网络的两个节点表示该工序的开始和结束，所述时间约束网络中的节点0表示所述初步可行调度计划的开始。

具体地，在已知生产批量计划的前提下，可以按照下述方式将炼钢-精炼-连铸生产调度计划描述成具有时间窗约束的调度问题：在该生产批量计划中，存在有n个工件{j₁，…，j_n}，每个工件ji包含{O_i1，O_i2，…，O_im}个工序，分别要顺序地通过m个生产阶段，并且在第1个生产阶段存在有|S1|台相同的设备，以供选择来进行加工。此外，假设同一工件在同一时间只能在一个设备上加工，同一设备在同一时间只能加工一个工件。工件在不同工序设备间转移需要已知的运输时间。此外，根据炼钢-精炼-连铸生产过程的工艺约束，不同工序间存在容量有限的缓冲区，工件在缓冲区停留时间不能超过设定值。除最后一道工序外，工件在各工序上完成加工后可以在该工序等待有限时间。并且，在最后一道工序，包含在同一批次中的工件必须按给定顺序在同一设备上连续加工。

根据以上描述，可以将炼钢-精炼-连铸生产过程的初步可行生产调度计划转化为时间约束网络图表示。

在该时间约束网络图中，节点代表各工件的不同工序，其中节点0和节点*为虚工序，分别代表整个初步可行生产调度计划的开始和结束，节点间的弧线代表各工件不同工序间的时间约束关系。

在该时间约束网络图中，节点间的时间约束关系可以分为以下3种：

1)同一设备上不同工序间的时间约束关系，通过虚线弧连接表示，箭头方向代表加工顺序，其被表示为时间约束[0，+∞]，表示前一工序加工完成后下一工序才能开始。例如图3所示，工序O₁₁、O₂₁被分配在第1生产阶段的第1台设备上，加工顺序为O₁₁→O₂₁，则它们间存在虚线弧连接[0，+∞]。

2)同一工件的不同工序在不同生产阶段上加工的时间约束关系，通过实线弧连接表示，其被表示为时间约束[t₁，t₂]，表示工件在上一设备加工完成后到下一设备开始的时间大于等于t₁，小于等于t₂，其中t₁由工件在设备间的运输时间决定，t₂由加工温度等工艺约束决定。例如图3所示，工件1的工序O₁₁完成后要转移到第2个阶段的某台设备上进行工序O₁₂，最小运输时间为5分钟，由于工艺温度的限制，最大间隔时间不能超过20分钟，则对应时间约束为[5，20]，表示炉次J₁在第一阶段设备上完成到第2阶段设备上开始的时间大于5分钟但小于20分钟。

3)在最后一道工序同一设备上不同工件的工序间的时间约束关系，通过实线弧连接表示，其被表示为时间约束[t₁，t₂]，表示上一工件加工完成后到下一工件到达的时间大于t₁，小于等于t₂，这里t₁、t₂由连铸工艺约束决定。最后1个生产阶段为连铸阶段，根据工艺要求，下一炉次必须在前一炉次加工完成前若干分钟到达。例如图3中的O₁₃到O₂₃间的时间约束[-5，-5]，表示J₂必须在J₁加工完成前5分钟到达该工位。

此外，通过将每个工序的开始、完成被划分成2个节点，可以将初步可行生产调度计划转换为时间约束网络。按照上述方式，可以得到如图3所示的时间约束网络，该时间约束网络实际包含38个节点，各节点含义如表1所示。

表1时间约束网络中各节点含义

  编号  代表事件  节点  代表事件  节点  代表事件  1  虚工序0  14  O₁₂开始  27  O₁₃完成  2  O₁₁开始  15  O₁₂完成  28  O₃₃开始  3  O₁₁完成  16  O₃₂开始  29  O₃₃完成  4  O₃₁开始  17  O₃₂完成  30  O₅₃开始  5  O₃₁完成  18  O₅₂开始  31  O₅₃完成  6  O₅₁开始  19  O₅₂完成  32  O₂₃开始  7  O₅₁完成  20  O₂₂开始  33  O₂₃完成  8  O₂₁开始  21  O₂₂完成  34  O₄₃开始  9  O₂₁完成  22  O₄₂开始  35  O₄₃完成  10  O₄₁开始  23  O₄₂完成  36  O₆₃开始

  编号  代表事件  节点  代表事件  节点  代表事件  11  O₄₁完成  24  O₆₂开始  37  O₆₃完成  12  O₆₁开始  25  O₆₂完成  38  虚工序*  13  O₆₁完成  26  O₁₃开始

这里要说明的是，所述初步可行调度计划可以预先根据所获得的生产批量计划生成并进行存储，也可以根据所获得的生产批量计划而实时生成。换言之，在步骤S210之前，在不存在初步可行调度计划的情况下，可以包含根据所获得的生产批量计划生成初步可行调度计划的步骤。或者，在已经存在初步可行调度计划的情况下，可以不包含根据所获得的生产批量计划生成初步可行调度计划的步骤。

在对初步可行生产调度计划进行如上转换后，流程进行到步骤S220。

在步骤S220，针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d_i0以及节点0与各节点i之间的最短时间距离d_0i，以获得各节点i的时间窗[-d_i0，d_0i]。

以下还是以图3中的时间网络图为例进行具体说明。

在将初步可行生产调度计划转换为时间网络图后，进一步将时间网络图中的时间区间约束表示为对应节点间的两条有向弧，在该有向弧上示出两个节点之间的时间距离值。例如，如图3所示的时间区间约束[0，+∞]，[20，22]，[-5，-5]和[137，137]就可以表示为图4中的4种有向弧。如图4所示，对应的节点间时间距离值分别为：a₁₂＝∞，a₂₁＝0，a₂₃＝22，a₃₂＝-20，a_27，32＝-5，a_32，27＝5，a_1，38＝137，a_38，1＝-137。

在如上获得时间约束网络中的节点i到节点j的距离为a_ij后，对转换后的时间约束网络应用Floyd-Warshall算法计算各节点间的最短时间间隔d_ij，该最短时间间隔d_ij表示计算出的节点i到节点j的最短距离。所述Floyd-Warshall算法流程如下：

[Floyd-Warshall算法]

For i：＝1 To n Do d_ii←0；

For i，j：＝1 To n Do d_ij←a_ij；

For k：＝1 To n Do

d_ij←min{d_ij，d_ik+d_kj}；

执行如上所述的Floyd-Warshall算法，计算出节点i到节点0的最短时间距离d_i0和节点0到节点i的最短时间距离。然后，将节点i的时间窗定义为[-d_i0，d_0i]。

在对时间约束网络图中的所有节点执行Floyd-Warshall算法后，可以获得各节点的时间窗。例如，在对图3所示的时间约束网络图中的所有节点执行Floyd-Warshall算法后，可以获得如表2所示的各节点的时间窗。

  编号  代表事件  时间窗口  节点  代表事件  时间窗口  节点  代表事件  时间窗口  1  虚工序0  [0，0]  14  O₁₂开始  [25，31]  27  O₁₃完成  [98，104]  2  O₁₁开始  [0，6]  15  O₁₂完成  [54，60]  28  O₃₃开始  [55，62]  3  O₁₁完成  [20，26]  16  O₃₂开始  [23，30]  29  O₃₃完成  [95，102]  4  O₃₁开始  [0，7]  17  O₃₂完成  [50，57]  30  O₅₃开始  [57，62]  5  O₃₁完成  [18，25]  18  O₅₂开始  [24，29]  31  O₅₃完成  [97，102]  6  O₅₁开始  [0，5]  19  O₅₂完成  [52，57]  32  O₂₃开始  [93，99]  7  O₅₁完成  [19，24]  20  O₂₂开始  [54，66]  33  O₂₃完成  [131，137]  8  O₂₁开始  [20，41]  21  O₂₂完成  [82，94]  34  O₄₃开始  [90，97]  9  O₂₁完成  [39，60]  22  O₄₂开始  [50，63]  35  O₄₃完成  [130，137]  10  O₄₁开始  [18，38]  23  O₄₂完成  [79，92]  36  O₆₃开始  [92，97]  11  O₄₁完成  [38，58]  24  O₆₂开始  [52，63]  37  O₆₃完成  [132，137]  12  O₆₁开始  [19，37]  25  O₆₂完成  [80，91]  38  虚工序*  [137，137]  13  O₆₁完成  [39，57]  26  O₁₃开始  [59，65]

表2各节点的时间窗表示

这里要说明的是，在本发明的实施例中，各节点的时间窗是采用Floyd-Warshall算法计算出的。但是，对于本领域技术人员而言，各节点的时间窗还可以采用其它合适的算法计算出。

在获得时间网络图中的各节点的时间窗后，流程进行到步骤S230。在步骤S230，根据所获得的各节点i的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划。

此外，要明白的是，所述方法还可以包括根据生产实际执行情况，对基于时间窗的生产调度计划进行更新(步骤S240)。

在步骤S240中，在将如上形成的基于时间窗的生产调度计划下发给生产厂后，可以收集实际的生产实绩，并判断该实际的生产实绩是否偏离生产调度计划。在该实际的生产实绩偏离生产调度计划，并对未来生产产生不利影响的情况下，可以根据生产实际执行情况调整工序、加工设备及加工顺序，由此在先前获得的时间约束网络中添加新的时间约束关系，从而重新计算各节点的时间窗口，并利用所计算出的各节点的时间窗，对所形成的基于时间窗的生产调度计划进行更新，从而保证生产过程的稳定性。

以上参照图2-图4以及具体实例对根据本发明实施例的基于时间窗的炼钢-精炼-连铸生产过程的调度方法进行了描述。

本发明的上述基于时间窗的炼钢-精炼-连铸生产过程的调度方法，可以采用软件实现，也可以采用硬件实现，或采用软硬件结合的方式实现。

图5示出了根据本发明实施例的基于时间窗的炼钢-精炼-连铸生产过程调度装置500的方框图。如图5所示，所述调度装置500包括时间约束网络生成单元501、计算单元503和生产调度计划形成单元505。

所述时间约束网络生成单元501用于基于初步可行调度计划，生成时间约束网络，其中所述初步可行调度计划中的各工序采用所述时间约束网络的两个节点来表示该工序的开始和结束，所述时间约束网络中的节点0表示所述初步可行调度计划的开始。这里要说明的是，在不存在初步可行调度计划的情况下，所述调度装置500还可以包括初步可行调度计划生成单元(图中未示出)，用于根据所获得的生产批量计划，生成所述初步可行调度计划。

在生成时间约束网络后，计算单元503针对所生成的时间约束网络，计算所述时间约束网络中各节点i与节点0之间的最短距离d_i0以及节点0与各节点i之间的最短时间距离d_0i，以获得各节点的时间窗[-d_i0，d_0i]。

在获得各节点的时间窗[-d_i0，d_0i]后，生产调度计划形成单元505根据所获得的各节点的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划。

此外，要说明的是，优选地，所述调度装置500还可以包括更新单元507，用于根据生产实际执行情况，对基于时间窗的生产调度计划进行更新。具体地，所述更新单元507可以在将如上形成的基于时间窗的生产调度计划下发给生产厂后，收集实际的生产实绩，并判断该实际的生产实绩是否偏离生产调度计划。在该实际的生产实绩偏离生产调度计划，并对未来生产产生不利影响的情况下，所述更新单元507可以根据生产实际执行情况调整工序、加工设备及加工顺序，由此在先前获得的时间约束网络中添加新的时间约束关系，从而重新计算各节点的时间窗口，并利用所计算出的各节点的时间窗，对所形成的基于时间窗的生产调度计划进行更新。

有益效果

通过以上结合附图对本发明实施例的详细描述，不难看出：利用本发明提供的基于时间窗的炼钢-精炼-连铸生产过程的调度方法和调度装置，可以基于初步可行调度计划，生成时间约束网络；针对所生成的时间约束网络，计算各节点i的时间窗[-d_i0，d_0i]；并根据所计算出的各节点i的时间窗[-d_i0，d_0i]，形成炼钢-精炼-连铸生产过程的基于时间窗的生产调度计划，从而使得生产管理人员不仅能够知道各工序的最早开始时间，同时也知道在不影响计划目标的前提下各工序的最晚开始时间，由此在生产过程中出现意外因素时及时对调度计划进行调整

但是，本领域技术人员应当理解，对上述本发明所提出的基于时间窗的炼钢-精炼-连铸生产过程的调度方法和调度装置，还可以在不脱离本发明内容的基础上做出各种改进。因此，本发明的保护范围应当由所附的权利要求书的内容确定。