Research on Moving Objects Indexing Method in Dynamic Environment

1.   引言

生产调度是制造业的一个重要环节，它对生产效率和资源利用率有着直接的影响。传统的生产调度一般分为大批量相同产品采取的Flow-shop调度^[1,2]和多品种小批量产品采取的Job-shop调度^[3,4]，这两类调度都将产品的加工和装配作为了两个独立阶段。随着社会对多品种小批量的产品需求越来越多，如果分别进行产品的加工和装配，必然割裂产品加工和装配内在并行处理的关系，将会降低产品的生产效率。为了满足当今社会对多品种小批量的产品需求，谢志强等人^[5–9]提出了第3类产品制造模式，将产品的加工和装配进行一同处理的综合调度。随着加工技术的发展，柔性制造在制造业中扮演着重要角色，柔性制造中工序的加工设备具有灵活性，更符合实际生产的需求。因此，本文提出了基于同层后道工序的柔性设备网络综合调度算法。

近年来对产品柔性制造调度的研究取得了一定的成果。针对柔性综合调度问题，Xie等人^[10]提出了综合柔性调度的分步式算法，该算法采取短用时策略为每个工序确定加工设备，缩小了工序加工设备的选择范围，但有可能导致多个工序的加工设备相同，使负载较重的加工设备形成生产瓶颈。Xie等人^[11]提出了基于静态处理时间的柔性综合调度算法，该算法在一定程度上降低了设备负载减少了瓶颈设备的出现，但是工序并行处理效果有一定的局限性，影响产品的完工时间。Yang等人^[12]针对柔性制造中同时具有设备柔性、工艺路线柔性和工序顺序柔性的多重柔性综合调度问题，提出考虑设备调整时间的多重柔性综合调度算法。谢志强等人^[13]提出一种考虑设备无关延迟约束的综合柔性调度算法，将设备无关延迟时间转换为设备无关延迟工序。谢志强等人^[14]提出一种基于设备驱动的综合柔性调度冲突调解算法(Conflict Mediation algorithm of the Integrated Flexible Scheduling based on Device Driver, DD-IFSCM)，该算法兼顾设备驱动策略和动态实质短路径策略的优点，较好地解决了综合柔性调度中设备与工序互选冲突问题，但工序并行处理没有得到保证影响了调度结果。谢志强等人^[15]提出一种基于设备驱动和实质路径的动态并行综合柔性调度算法(Dynamic Parallel Integrated Flexible Scheduling algorithm based on Device Driver and Essential Path, DDEP-DPIFS)，该算法提高了工序并行处理率，忽略了串行工序的紧密度影响了产品完工时间。谢志强等人^[16]提出一种基于逆序层优先的柔性综合调度算法(Flexible Integrated Scheduling algorithm based on Reverse Order Layer Priority, ROLP-FIS)，该算法采用逆序调度的思想，从根节点开始调度，这样可以简化某一工序存在多紧前工序的约束条件，便于合理安排各工序，但其加工设备选择中设备抢占策略对其影响的工序后移，影响了调度结果。Yang等人^[17]提出具有双向协调机制的柔性综合调度算法(a Signal-Driven based Flexible Integrated Scheduling Algorithm with bidirectional coordination mechanism, SD-FISA)，该算法设计的设备-工序协调机制可以根据驱动时刻设备和工序的实际调度情况分配两者的选择权，并在其出现冲突时采用最优组合策略进行化解。Gao等人^[18]提出一种基于剩余加工时间概率选择编码的柔性综合调度算法，该算法的编码方法是基于剩余加工时间概率选择的，保证了初始种群的可行性，多样性以及优良性。Xie等人^[19]提出了基于网络设备协作的柔性综合调度问题的改进人工蜂群算法，解决了综合调度智能优化算法中编码方式遗漏最优解的问题。

在上述柔性综合调度算法中，DD-IFSCM算法和DDEP-DPIFS算法都是从设备选择工序的角度进行调度，并且均是正向调度，除了根节点以外每一个工序均有紧前工序，当一个工序有多个紧前工序时，难以合理安排多个紧前工序，使产品完工时间受到影响。ROLP-FIS算法是从工序选择设备的角度进行调度，该算法中当工序选择设备时，其短用时设备有空隙就进行抢占，影响了后续工序加工，忽略了柔性设备的灵活性，使产品完工时间受到影响。SD-FISA算法没有综合考虑工序在柔性设备上的加工用时，当在驱动时刻设备与工序组合存在冲突时，未考虑对后续工序的影响。本文从工序选择设备的角度，设计了使工序充分串并行处理和缩短产品完工时间的柔性设备网络综合调度算法。该算法首先采用了逆序层优先策略和均值逆序紧后路径策略，确定了各逆序层待调度工序集中工序的调度顺序，提高了同层工序的并行处理；然后采用了最早完工时间策略和设备空闲插入策略为工序选择加工设备，没有选择最短处理时间的加工设备，而是选择了使工序实现更短完工时间的设备，同时在选择设备时考虑了在柔性设备上的加工时间和同层后道工序的加工设备，提高了工序并行处理效率和串行处理紧密度，缩短了产品的完工时间。

2.   问题描述分析

柔性设备网络综合调度中设备网络布局已知，工件工序已知，工序之间的约束关系不能改变；每个工件的每道工序对应的加工设备与加工时间已知。柔性设备网络综合调度中复杂产品加工工序呈树状结构，称为产品加工工艺树，工序间的有向边为产品加工的偏序关系。柔性设备网络综合调度满足以下要求：

(1)工序的加工和装配统一为加工；设备网络中的加工设备和装配设备统一为加工设备。

(2)每个工序具有工序序号、可用加工设备和在加工设备上需要的加工用时。

(3)设备网络中的设备在同一时刻只能加工1道工序。

(4)每个工序只能被1台加工设备加工，某一道工序开始加工则不能被打断。

(5)设备网络中不存在相同设备，并且加工设备呈离散分布状态，加工设备间的运输时间不考虑。

(6)每道工序都必须在其所有紧前工序加工完毕后，方可开始加工。

(7)产品的加工总用时为最晚结束加工工序加工完工的时间与最早开始加工工序的加工开始时间之差。

定义1　逆序加工工艺树：将加工工艺树的有向边取反之后所得的树形结构。

定义2　层待调度工序集：将加工工艺树按层划分，得到的每一层工序组成的集合。

定义3　逆序紧前工序：在逆序加工工艺树中，原本加工工艺树中某一工序的紧后工序成为该工序的紧前工序，称为逆序紧前工序。

定义4　逆序紧后工序：在逆序加工工艺树中，原本加工工艺树中某一工序的紧前工序成为该工序的紧后工序，称为逆序紧后工序。

定义5　同层后道工序：将加工工艺树按层划分，同层工序中除最后一道工序以外，目标工序的下一个工序，称为同层后道工序。

定义6　均值逆序紧后路径：按平均加工时间计算时，为目标工序所有逆序紧后工序加工到叶节点的最大值与目标工序在柔性设备上加工时间均值的和。

定义7　平均加工时间：在逆序加工工艺树中，工序在柔性设备上的平均加工时间。

柔性设备网络综合调度问题的数学模型可以描述为：假设产品有n道工序${\{ {A_i}\} _{_{1 \le i \le n}}}$，需要在m台加工设备${\{ {M_j}\} _{1 \le j \le m}}$上进行加工。${\text{AF}}{{\text{T}}_{ij}}$表示工序${A_i}$在加工设备${M_j}$上实际完工时间； ${H_{ij}} = 1$表示工序${A_i}$在加工设备${M_j}$上加工；${t_{ij}}$表示工序${A_i}$在加工设备${M_j}$上的加工时间；${s_i}$表示工序${A_i}$的开始加工时间；${f_i}$表示工序${A_i}$的完工时间；${t_i}$表示工序${A_i}$的加工用时； $x \in {\text{pred(}}i{\text{)}}$表示工序${A_x}$是工序${A_i}$的逆序紧前工序； $y \in {\text{succ(}}i{\text{)}}$表示工序${A_y}$是工序${A_i}$的逆序紧后工序。柔性设备网络综合调度的目标是最小化最大完工时间，因此该问题的数学描述为

s.t

其中，式(1)为目标函数，即最小化最大完工时间；式(2)表示每道工序只能被1台加工设备加工；式(3)为工序${A_i}$的加工时间；式(4)为工序${A_i}$的完工时间；式(5)为工序${A_i}$的加工开始时间一定大于或等于其逆序紧前工序的加工结束时间，并使工序${A_i}$尽早开始加工；式(6)为工序${A_i}$的加工结束时间一定小于或等于其逆序紧后工序的最小加工开始时间；式(7)表示工序${A_i}$与工序${A_l}$在同一个加工设备上进行加工，后一道工序的开始时间大于或等于前一道工序的加工结束时间。

3.   策略分析

在解决柔性设备网络综合调度问题时，根据逆序加工工艺树特点可知，调度各工序时需要严格遵守工序间的偏序关系，除此之外柔性设备网络综合调度问题中对加工设备进行合理选择也是十分重要的。为了使产品加工用时尽可能小，本文提出了考虑同层后道工序的柔性设备网络综合调度算法(Integrated Scheduling algorithm for Flexible Equipment Network considering Same layer after the Process, SP-FENIS)，首先根据逆序层优先策略和均值逆序紧后路径策略进行工序排序；然后根据最早完工时间策略和设备空闲插入策略为各个工序选择加工设备，确定了各个工序的加工设备以及加工时间；最后生成产品调度方案。

3.1   逆序层优先策略

逆序层优先策略^[16]将各工序分配至逆序层待调度工序集。首先，从逆序加工工艺树的根结点开始按层进行划分，即根结点为第1层，其所有逆序紧后工序的层数为第2层，依次类推；然后将每一层的工序放入逆序层待调度工序集中；最后，从第1层开始依次对各层工序进行调度。逆序层优先策略的优势：(1)将加工工艺树中所有偏序关系逆置，得到逆序加工工艺树，在逆序加工工艺树中除根节点以外，每一工序均有逆序紧前工序，只有根结点没有逆序紧前工序，所以第1个工序最早加工开始时间和最早结束时间很容易被确定，而且每一个工序具有唯一逆序紧前工序，解决了难以确定工序加工开始时间的问题。(2) 按层调度提高了同层工序的并行处理。

3.2   均值逆序紧后路径策略

均值逆序紧后路径策略确定了各逆序层待调度工序集中工序的调度顺序，均值逆序紧后路径为目标工序所有逆序紧后工序加工到叶结点的最大值与目标工序在柔性设备上加工时间均值的和，其公式如式(8)所示。逆序加工工艺树叶节点没有逆序紧后工序，其均值逆序紧后路径为其在柔性设备上加工时间均值。工序排序按逆序待调度工序集中各工序的均值逆序紧后路径值进行降序排序，优先调度均值逆序紧后路径值大的工序；当均值逆序紧后路径值相同时，优先调度逆序紧后工序个数多的工序；如果逆序紧后工序个数也相同，随机选择工序。均值逆序紧后路径策略提高了纵向加工工序的紧密度

其中，${{\overline t_i}}$为工序在柔性设备上的平均加工时间；工序${A_j}$为工序${A_i}$的逆序紧后工序； $T({A_i})$为工序${A_i}$的均值逆序紧后路径。

3.3   最早完工时间策略

由于柔性设备网络综合调度问题中工序加工设备的不唯一性，为了使工序选择合适的加工设备，SP-FENIS算法设计了最早完工时间策略，没有选择最短处理时间的加工设备，而是选择使工序实现更短的完工时间的设备，同时考虑了在柔性设备上的加工时间和同层后道工序的加工设备，确定了目标工序的加工设备以及加工时间。最早完工时间为工序在相应设备上最早开始时间与其在相应设备上加工时间之和，其公式如式(9)所示。最早完工时间策略使工序充分并行，进而缩短了产品完工时间。最早完工时间策略为各个工序选择加工设备，优先选择早完工的设备；如果目标工序在不同加工设备上完工时间相同，则优先选择加工用时短的加工设备；如果在不同加工设备上用时也相同，则优先选择和同层后道工序短用时设备不同的加工设备；如果加工设备与同层后道工序短用时设备都不同，则随机选择加工设备

其中，${\text{EF}}{{\text{T}}_{ik}}$为工序${A_i}$在加工设备${M_k}$上最早完工时间；${\text{ES}}{{\text{T}}_{ik}}$为工序${A_i}$在加工设备${M_k}$上最早开始时间；${\text{AF}}{{\text{T}}_{jk}}$为工序${A_j}$在加工设备${M_k}$上实际完工时间；${t_{ik}}$为工序${A_i}$在加工设备${M_k}$上加工时间；${T_{{\mathrm{avl}}}}({M_k})$为设备${M_k}$最早准备就绪时间。

3.4   设备空闲插入策略

为了提高设备利用率和缩短产品完工时间，SP-FENIS算法提出了设备空闲插入策略。工序对设备进行抢占是由于目标工序的逆序紧前工序完工时，目标工序的短用时设备存在空闲，并且该设备的空闲时间大于等于目标工序在该设备上的加工时间。目标工序进行设备空闲插入须满足的条件是目标工序的短用时设备存在空闲，该加工设备已经安排的工序最早开始时间与设备最早准备就绪时间之间的差值大于等于目标工序在该设备上的加工时间。设备空闲插入策略使并行工序充分并行处理缩短了产品完工时间。

4.   算法设计及复杂度分析

4.1   算法设计

考虑同层后道工序的柔性设备网络综合调度算法实现步骤如下所示，算法流程图如图1所示。

图  1  SP-FENIS算法流程图

下载: 全尺寸图片 幻灯片

步骤1　输入加工设备和产品加工信息，计算各个工序的平均加工时间以及均值逆序紧后路径。

步骤2　执行逆序层优先策略，按各个工序所在的层数将其分配至不同的的逆序层待调度工序集，从第1层开始依次对各层工序进行调度，假设一共有$z$层，第1层为$p = 1$。

步骤3　判断$p$是否大于$z$，如果是，则执行步骤12；否则执行步骤4。

步骤4　计算第$p$层中各个工序的均值逆序紧后路径值，执行均值逆序紧后路径策略，将第$p$层中待调度工序进行降序排序。

步骤5　判断当前逆序层待调度工序集${O_i}$是否为空，如果为空，则执行$p = p + 1$，并执行步骤3；否则，执行步骤6。

步骤6　依次获取当前逆序层待调度工序集中的工序作为目标工序。

步骤7　判断当前逆序层待调度工序集工序数${\text{length}}({O_i})$是否大于1并且当前待调度工序是否是首个工序，如果${\text{length}}({O_i}) > 1$且$i > 1$，则执行步骤9；否则，执行步骤8。

步骤8　执行最早完工时间策略，计算目标工序在柔性设备上的最早完工时间，根据最早完工时间为目标工序确定了加工设备以及加工时间，跳转至步骤5。

步骤9　判断目标工序的最短用时设备${\text{st\_set}}$是否空闲，如果空闲，则执行步骤10；否则执行步骤8。

步骤10　如果设备${\text{st\_set}}$已经安排了工序${A_j}$，${A_j}$最早开始时间与设备最早准备就绪时间之间的差值大于等于目标工序${A_i}$在该设备上的加工时间${\text{EST(}}{A_j},{\text{st\_set)}} - {T_{{\mathrm{avl}}}}({\text{st\_set}}) \ge t({A_i},{\text{st\_set}})$且目标工序${A_i}$的逆序紧前工序的完工时间小于设备最早准备就绪时间${\text{PRE(}}{A_i},{\text{st\_set) < EST(}}{A_j},{\text{st\_set)}}$，则执行步骤11；否则，执行步骤8。

步骤11　执行设备空闲插入策略确定目标工序加工开始时间和结束时间以及加工设备，跳转至步骤5。

步骤12　结束。

4.2   复杂度分析

假设复杂产品的加工工序数为$n$，加工设备数为$m$，本算法主要有以下操作：

(1)逆序层优先策略：根据逆序加工工艺树中工序的偏序关系，依次确定逆序加工工艺树的各层节点，将其放入逆序层待调度工序集中，需要执行$n$次，逆序层优先策略的时间复杂度为$O(n)$ 。

(2)均值逆序紧后路径策略：首先，计算工序在柔性设备上的平均加工时间，需要执行$m$次，共$n$道工序，计算每道工序的平均加工时间复杂度为$O(n \times m)$ ；然后计算每道工序均值逆序紧后路径值，共$n$道工序，其时间复杂度为$O(n)$；最后对逆序层待调度工序集中工序按均值逆序紧后路径值进行排序，时间复杂度为 。均值逆序紧后路径策略的时间复杂度为$O(n\log _2\;n)$。

(3)最早完工时间策略：由于每个工序最多可在$m$台加工设备上加工，因此在进行最早完工时间设备选择时最多需要执行$m$次操作，因此最早完工时间策略的时间复杂度为$O(n \times m)$。

(4)设备空闲插入策略：确定工序用时最短的设备在工序最早可加工时间是否空闲，如果满足插入条件，则工序进行插入，其设备空闲插入策略的时间复杂度$O(n)$。

综上所述，SP-FENIS算法的时间复杂度为$O(n\log _2\;n)$。

5.   实例对比分析

为了方便读者理解算法，下面通过实例进行对比分析。SP-FENIS 算法不以具体实例为依据，具有普遍意义。设有产品A，由20道工序组成，分别在4台柔性加工设备上进行加工，其产品工艺树如图2所示。下面分别使用DD-IFSCM 算法^[14]、DDEP-DPIFS算法^[15]、ROLP-FIS算法^[16]、SD-FISA算法^[17]和SP-FENIS算法分别调度产品A，并对比调度甘特图说明算法特点。

图  2  产品A逆序加工工艺树

下载: 全尺寸图片 幻灯片

DD-IFSCM算法设备驱动时刻按最短加工用时确定工序，当设备冲突时使用冲突调解策略选择尽早结束的组合方案调度；当存在一个空闲设备有多个可调度最短加工工序时，采用动态实质短路径策略选择尽早结束的工序加工。DD-IFSCM算法调度甘特图如图3所示，加工总用时为150个工时。DDEP-DPIFS算法采用空闲设备驱动策略动态确定并行工序，对并行工序按提出的并行优化策略和最早加工结束策略确定加工设备；当存在一个空闲设备有多个可调度最短加工工序时，采用实质短路径策略选择工序加工。DDEP-DPIFS算法调度甘特图如图4所示，加工总用时为140个工时。ROLP-FIS算法根据逆序层优先策略和动态长路径策略确定了工序调度顺序，然后根据设备选择策略和设备抢占策略确定了加工设备和加工时间。ROLP-FIS算法调度甘特图如图5所示，加工总用时为140个工时。SD-FISA算法根据双向调度策略和基于灰色关联分析的设备-工序协调策略得到了工序-设备组，当设备与工序组合存在冲突时根据最优组合策略确定设备-工序组合。SD-FISA算法调度甘特图如图6所示，加工总用时为140个工时。

图  3  DD-IFSCM算法调度产品A所得甘特图

下载: 全尺寸图片 幻灯片

图  4  DDEP-DPIFS算法调度产品A所得甘特图

下载: 全尺寸图片 幻灯片

图  5  ROLP-FIS算法调度产品A所得甘特图

下载: 全尺寸图片 幻灯片

图  6  SD-FISA算法调度产品A所得甘特图

下载: 全尺寸图片 幻灯片

SP-FENIS算法调度产品A的调度过程如下：

步骤1　根据逆序层划分策略，将各工序分配至逆序层待调度工序集，产品A共有7个逆序层待调度工序集分别为：第1层逆序层待调度工序集为${L_1} = \{ {\text{A20}}\}$、第2层逆序层待调度工序集为${L_2} = \{ {\text{A18}},{\text{A19}}\}$、第3层逆序层待调度工序集为${L_3} = \{ {\text{A15}},{\text{A16}},{\text{A17}}\}$、第4层逆序层待调度工序集为${L_4} = \{ {\text{A11}},{\text{A12}},{\text{A13}},{\text{A14}}\}$、第5层逆序层待调度工序集为${L_5} = \{ {\text{A6}},{\text{A7}},{\text{A8}},{\text{A9}},{\text{A10}}\}$、第6层逆序层待调度工序集为${L_6} = \{ {\text{A3}},{\text{A4}},{\text{A5}}\}$和第7层逆序层待调度工序集为${L_7} = \{ {\text{A1}},{\text{A2}}\}$。

步骤2　根据均值逆序紧后路径策略，首先计算了产品A中每个工序的平均加工时间和均值逆序紧后路径值如图7所示；然后在确定每层工序的逆序紧前工序的完工时间；最后根据计算的均值逆序紧后路径值确定了各逆序层待调度工序集中工序的调度顺序分别为：第1层中工序的调度顺序为$\{ {\text{A20}}\}$、第2层中工序的调度顺序为$\{ {\text{A19}},{\text{A18}}\}$、第3层中工序的调度顺序为$\{ {\text{A17}},{\text{A16}},{\text{A15}}\}$、第4层中工序的调度顺序为$\{ {\text{A14}},{\text{A12}},{\text{A11}},{\text{A13}}\}$、第5层中工序的调度顺序为$\{ {\text{A9}},{\text{A7}},{\text{A10}},{\text{A8}},{\text{A6}}\}$、第6层中工序的调度顺序为$\{ {\text{A4}},{\text{A3}},{\text{A5}}\}$和第7层中工序的调度顺序为$\{ {\text{A1}},{\text{A2}}\}$。

图  7  产品A各工序平均加工时间和均值逆序紧后路径值

下载: 全尺寸图片 幻灯片

步骤3　根据最早完工时间策略和设备空闲插入策略，确定了目标工序的加工设备以及加工时间，形成了产品A的调度方案，如表1所示。

表  1  SP-FENIS算法调度产品A的调度过程

逆序待调度 工序集	工序号	EFT				所选加工设备
		M1	M2	M3	M4
A20	A20	25	15	null	20	M2
A19,A18	A19	null	35	40	null	M2
	A18	30	null	40	35	M1
A17,A16, A15	A17	55	null	60	55	M4(工序A17在M1,M3上最早完工时间和加工用时都相同，根据同层后道工序A16的短用时设备M1进行选择，选择与同层后道工序的短用时设备不同的加工设备M4)
	A16	50	null	60	null	M1
	A15	null	60	50	80	M3
A14,A12, A11,A13	A14	null	95	null	75	M4
	A12	70	null	70	120	M3(工序A12在M1,M3上最早完工时间和加工用时都相同，同时没有与同层后道工序的短用时设备相同的加工设备，则进行随机选择，选择M3)
	A11	null	80	null	95	M2
	A13	65	100	null	90	M1
A9,A7,A10, A8,A6	A9	105	100	100	null	M2(工序A9在M2,M3上最早完工时间相同，在M2上加工用时短，选择M2)
	A7	null	130	85	95	M3
	A10	95	125	110	null	M1
	A8	115	null	100	100	M3(工序A8在M2,M3上最早完工时间相同，在M3上加工用时短，选择M3)
	A6	110	null	120	null	M1
A4,A3,A5	A4	140	null	null	120	M4
	A3	125	130	120	null	M3
	A5	null	120	135	160	M2
A1,A2	A1	null	null	140	130	M4
	A2	130	135	null	null	M1

下载: 导出CSV 

| 显示表格

SP-FENIS算法调度甘特图如图8所示，加工总用时130 个工时。与DD-IFSCM算法、DDEP-DPIFS算法、ROLP-FIS算法和SD-FISA算法相比，SP-FENIS算法调度产品A所得的完工时间更短。DD-IFSCM算法的调度结果之所以不理想, 是因为DD-IFSCM算法在工序进行加工设备选择出现冲突时，选择了整体加工时间短的组合调度方案，没有考虑到工序在工艺树中的相对位置影响了调度结果。例如，当驱动时刻为0时，驱动加工设备M1可预调度工序为A2；驱动加工设备M2可预调度工序也为A2；此时发生了设备冲突，继续从可调度工序集中分别为加工设备M1和M2寻找除A2以外的短用时工序，寻找结果分别为A6, A5；根据冲突调节策略为了整体加工时间最短，选择A6在加工设备M1上加工，A2在加工设备M2上加工；事实上，A2在加工设备M1上加工用时最短，但没有选择在用时最短的加工设备上加工，影响了其后续工序的调度，最终导致调度结果不理想。 DDEP-DPIFS算法的调度结果之所以不理想, 是因为DDEP-DPIFS算法只关注工序加工设备的闲忙和工序的实质短路径, 没有综合考虑工序在柔性设备上的加工用时以及其在工艺树中的相对位置，并且DDEP-DPIFS算法过于依赖工序的最短加工时间等因素对调度结果的影响。例如，工序A10和工序A9为同层工序并同为工序A14的紧前工序，工序A10和工序A9都在加工设备M2上加工，使同层工序没有充分并行处理，影响了紧后工序A14的开始加工时间，进而影响了其后续工序的调度，最终导致调度结果不理想。ROLP-FIS算法的调度结果之所以不理想, 是因为ROLP-FIS算法设备抢占策略对影响到的工序进行后移，影响了其后续工序的调度，同时使并行工序没有充分并行处理，导致调度结果的不理想。 例如, 工序A16抢占工序A17加工设备M1，导致工序A17完工时间推后影响了后续工序，同时工序A16与工序A17没有充分并行处理，最终导致调度结果不理想。SD-FISA算法的调度结果之所以不理想, 是因为SD-FISA算法没有综合考虑工序在柔性设备上的加工用时，当在驱动时刻设备与工序组合存在冲突时，未考虑对后续工序的影响，导致调度结果不理想。例如，当驱动时刻为85时，空闲设备有M1, M3和M4，可调度工序有A3, A6和A10，工序A3和A10有后续工序，此时设备与工序组合存在冲突，根据最优组合策略确定设备-工序组合，最终确定工序A3在设备M1上加工，工序A6在设备M3上加工，工序A10在此驱动时刻未被加工影响了后续工序的调度，最终导致调度结果不理想。SP-FENIS算法相比于DD-IFSCM算法、DDEP-DPIFS算法和SD-FISA算法，综合考虑了工序在工艺树中的相对位置，并对设备进行了合理选择，提高了工序并行处理效率和串行处理紧密度； SP-FENIS算法相比于ROLP-FIS算法，SP-FENIS算法中的平均加工时间相比ROLP-FIS算法中的拟加工时间更能反映出柔性加工设备之间加工时间的差异，SP-FENIS算法工序A17进行设备选择时考虑了同层后道工序A16的短用时设备，使工序A17与工序A16充分并行处理，减少了对工序A17后续工序的影响，使完工时间更短。该算法在不提高算法复杂度和运行时间的前提下，缩短了产品完工时间。

图  8  SP-FENIS算法调度产品A所得甘特图

下载: 全尺寸图片 幻灯片

6.   结论

针对柔性设备网络综合调度中设备选择影响产品完工时间的问题，SP-FENIS算法既提高了并行工序的并行处理，又提高了串行工序的紧密度，缩短了产品完工时间，结论如下：

(1)逆序层优先策略将各工序分配至逆序层待调度工序集；

(2)均值逆序紧后路径策略根据均值逆序紧后路径值对各个工序进行排序；

(3)最早完工时间策略和设备空闲插入策略确定了各个工序的加工设备以及加工时间，同时考虑了同层后道工序的加工设备使同层工序充分并行。

综上所述，考虑同层后道工序的柔性设备网络综合调度算法为解决柔性设备网络综合调度问题提供了新方法和拓展了新思路，具有一定的理论和实际意义。