考虑层级调度次序的资源协同综合调度算法

谢志强，周 伟，杨 静

(1.哈尔滨理工大学 计算机科学与技术学院,黑龙江 哈尔滨 150080；2.哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)

0 引言

产品调度问题是对有限设备、人员等资源进行调配，以获取最优的时间效率和设备使用率为目的的活动。调度效果直接影响企业的生产效率和社会效益，具有重要的研究意义，受到了社会学、管理学、运筹学等领域专家的一致关注。

在20世纪初期，任务的调度和分配被认为是一个基于图论、数学程序设计方法、启发式方法等的问题[1]。1967年，CONWAY等[2]发表的文献被公认为调度理论研究的标志性文章。70年代，调度研究的标志性工作是其理论研究已发展成为一门系统的应用学科，但未开展深入的实践研究。80年代，调度研究的标志性工作是在应用领域开展的研究已经能够解决实际问题。例如SCHUSTER等[3]用线性规划方法解决了材料的调度分配等。

随着调度工作从理论到实践的发展，人工智能、智能控制等调度方法迅速发展。学者们针对调度及调度效率问题进行了大量的研究，根据加工的难易程度，可分为单机调度、车间调度、流水线车间调度、开放式车间调度等，例如陈乔鑫等[4]设计了一种车载边缘计算中推理任务实时调度策略，李明等[5]采用新型帝国竞争算法提出了考虑准备时间和关键目标的柔性作业车间调度问题。根据加工的任务特征，可分为静态和动态两种调度。根据优化的方法策略，可分为数学规划、虚拟仿真、控制理论等，例如李小林等[6]针对考虑工件释放时间和柔性维护的单机调度问题，建立了整数规划模型并进行线性化，杨艳芳等[7]对具有工序刚性约束的装配线提出了基于并行工位设计和装配序列规划的多目标优化方法。根据调度问题所采用的计算机算法，可分为专家系统算法、人工神经网络算法、智能搜索算法、目标任务算法、云计算和大数据算法等，例如徐洪智等[8]解决了异构多处理器系统执行并行任务时最小化系统资源并保证可靠性的问题，郝春亮等[9]运用大数据技术完成了集群调度的4种结构问题，胡晓阳等[10]针对受运输时间和运输资源约束的柔性作业车间调度问题，提出一种融合贪心启发式规则的改进迭代局部搜索算法，郭伟飞等[11]提出了基于设计结构矩阵和遗传算法的综合调度算法，文一凭等[12]构建了云际协作环境下能耗与成本感知的工作流调度模型，并提出一种相应的云工作流调度方法。

本文在同时考虑加工和装配的综合调度领域，针对多品种单件或小批量的树状复杂产品的调度问题，提出了一种考虑层级调度次序的资源协同综合调度算法。算法提出了同层工序数较多的复杂产品如何提高设备利用率、缩短总加工用时的问题并给出了建模；具体阐述了算法中的优先级调度策略、叶节点调度策略和短用时调度策略；利用Petri网进行了调度设计和仿真实验；最后通过实验对比分析表明了本文算法的有效性。

1 研究背景

随着调度相关研究的不断深入，沈亚菲等[13]首次提出了关于多品种、小批量生产的调度问题，采用人为控制调度区间的加班算法压缩了加工工时。

为了更好地解决多品种、小批量复杂产品调度问题，文献[14]提出了将“单件或小批量产品加工和装配一同处理的综合调度”[14]，并针对调度的优化算法开展了系统的深入研究[15-19]，取得了较丰富的成果。代表性成果如下：文献[19]采用考虑串行工序择时的算法，在纵横兼顾的基础上进一步优化了调度算法，但是当相同设备上出现叶节点工序时，串行工序序列间会产生很多无法利用的加工空隙；文献[20]提出了拟关键路径的算法，该算法在考虑加工工序约束关系的前提下，以产品纵向加工为主线构建关键路径，并对关键路径上的工序进行优先加工，但是这种方法没能考虑横向工序对调度结果的整体影响；文献[21]提出考虑后续工序的择时算法，虽然考虑了工序间紧前紧后工序的制约关系，也考虑到了串行和并行工序对调度工序的整体影响，但是忽略了对空闲设备的充分利用；文献[22]采用可动态生产具有优先级工序集的算法，在纵横兼顾的基础上进一步优化了调度算法，但是采用动态思想的算法仍然以纵向调度为主线，降低了具有约束关系的紧前紧后工序之间的衔接度。

上述综合调度算法虽然提高了树状复杂产品的调度效果，但是以纵向加工为主的思想，忽略了横向同层工序对复杂产品总体调度的影响，使得工序间紧前紧后约束关系和设备利用率都受到了影响。

针对同层工序数较多的树状复杂产品，本文提出了一种考虑层级调度次序的资源协同综合调度算法。算法在层优先原则的前提下，充分考虑加工工序自身属性，通过优先调度同层叶节点工序和加工用时较短工序的算法，兼顾了产品工艺树中横纵的并行问题，进一步充分利用了设备的空闲时间。再将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，通过算法计算并赋予Token值，完成触发变迁，仿真实现综合调度。

2 问题及建模

根据文献[14]的定义，将加工设备和装配设备统一定义为设备，将加工和装配统一定义为加工[14]；用树状结构表示产品加工工艺，树中节点对应加工工序，包含加工时间、加工设备及加工的顺序等信息，并且要求必须满足：

(1)工序和设备具有唯一匹配性；

(2)设备加工工序时，具有时间确定性，即某一时刻设备只能加工一道工序；

(3)每道工序可以被加工的充分必要条件是其所有紧前工序均加工完毕或者没有紧前工序；

(4)工序加工具有连续性，即工序从开始加工直到加工结束是一个完整且连续的过程；

(5)所有工序加工完毕的总用时为产品的总加工时间。

假设某个复杂产品A加工工艺树如图1所示，包含11道加工工序；树状结构中的每个节点表示加工工序：A1～A11。每个工序包含3种信息，分别是工序序号、工序对应的加工设备序号和工序自身加工用时。箭头表示工序的紧前紧后约束关系，如工序A1在设备M2上加工，加工用时为4工时，其紧前工序为工序A7和A8，紧后工序为工序A3。即工序A5必须在工序A7和A8全部加工结束后，才可以开始加工，而工序A3必须在工序A5加工结束后才可以开始加工。

假设复杂产品共有n个工序，在m台设备上加工，综合调度的已知条件为：

(1)n个加工工序序列{P1,P2,…Pn}；

(2)m台加工设备序列{M1,M2,…Mn}；

(3)每个工序自身加工时间ti(其中1≤i≤n)。

约束条件为：除了叶节点工序具有紧后工序、根节点工序具有紧前工序以外，其他所有节点工序均存在紧前紧后工序约束关系，在一道工序连续加工完成后，其后序约束工序才可以开始加工。

求解问题为：合理调度各个工序，确定各工序的开始加工时间，使得复杂产品总体加工用时更少。

建立如下问题模型：

资源条件：

P(i+1)m-Pim≥0；

(1)

约束条件：

STi+1-STi≥ti；

(2)

求解问题：

α,β∈[0,1]。

(3)

其中：

Pim表示第m个设备上正在加工的第i个工序；

STi表示第i个工序开始加工时间；

Ti表示复杂产品加工总用时；

PTi表示第i个工序的层优先级；

LN表示叶节点工序。

式(1)表示在同一设备m上第i个工序加工完成后第i+1个工序才可以开始加工；式(2)表示工序间的紧前约束关系，STi为第i个工序开始加工时间；式(3)表示求解问题为使得复杂产品总体加工用时Ti最少，包括工序的层优先级PTi、工序是否为叶节点工序和工序自身加工时间ti等因素，其中α为叶节点工序的判断系数，β为同层自身加工用时较短的工序判断系数。因为本文算法包含短用时策略，所以不选取β=0的情况。无论叶节点工序还是非叶节点工序，当其不唯一时都需要判断工序自身加工用时，即存在α=0∩β=1和α=1∩β=1两种情况。

3 算法设计

3.1 算法描述

因为紧前工序的优先调度对加快整个产品的调度过程至关重要，所以本文考虑层级调度次序的综合调度算法提出优先级调度策略、叶节点调度策略和短用时调度策略三级判断机制。通过优先级调度策略的工序最早开始加工思想、叶节点调度策略的减少设备空闲时间段思想和短用时调度策略的提高工序间紧密度思想的综合运用来提高设备利用率，从而达到缩短复杂产品总加工用时的优化目的。具体描述如下：

步骤1根据工艺树的结构特征，确定工艺树的层序，并设置优先级。

步骤2判断优先级最高的节点工序是否唯一，如果是，则根据优先级调度策略调度优先级高的工序，如果否，则转步骤3。

步骤3当优先级相同的工序不唯一时，根据叶节点调度策略进行选择，调度优先级相同的叶节点工序。

步骤4若以上3个步骤仍然不能唯一确定加工工序时，根据短用时策略调度自身加工用时较短的工序；直到所有工序全部加工结束，算法框架流程图如图2所示。

3.2 优先级调度策略

根据“减少并行工序加工时间”原则，文献[23]针对复杂产品工艺树中的加工工序提出了工序优先级问题，即将工序调度的优先顺序定义为工序的优先级[23]。假设产品加工工艺树有n层，则将根节点工序的优先级定义为1；根节点工序的所有后裔节点工序的优先级定义为2，同层工序节点作为兄弟节点；以此类推，直到第n层所有节点的优先级定义为n。定义根节点工序的优先级最低，第n层上工序的优先级最高。

优先级策略具有两点优势：①可以最早开始加工约束力强的紧前工序；②优先级调度策略是以“层”为单位，不限制加工工序必须都在同一设备上加工。

3.3 叶节点调度策略

无论工序节点位于复杂工艺树的哪一层，只要没有紧前工序的节点，均视为叶节点。如前所述，确定了各工序的层优先级后，若存在层优先级相同的工序{Pm1,Pm2,…Pmn}，则判断{Pm1,Pm2,…Pmn}序列中是否存在叶节点，若存在且唯一存在Pm1(1≤i≤n)为叶节点，则优先调度。

叶节点工序调度策略具有两点优势：①叶节点工序的优先调度能够带动其后续所有工序均较早开始加工；②因为叶节点工序没有紧前工序的约束，所以能够充分利用设备的空闲时间，从而提高设备的利用率。

3.4 短用时调度策略

根据“设备忙”原则，文献[22]指出在相同设备上加工的工序序列，当工序具有相同的路径长度时应该调度用时少的工序。

在叶节点工序优先调度策略的基础上，引入短用时调度策略，即若在加工工艺树的第i层上，存在工序{Pi1,Pi2,…Pin}均为叶节点工序时，则优先调度自身加工用时较短的工序。短用时调度策略具有两点优势：①充分利用了工序自身加工用时的属性；②提高了工序间的紧密度。

3.5 算法复杂度分析

假设复杂产品的加工工序数、加工设备数和每道工序的自身加工用时等信息均已知，分别设为n、m、t，则本文算法复杂度分析如下：

(1)将复杂产品的加工工艺图转化为工艺树，树中节点对应工序，约束关系对应节点位置，确定根节点为最后一道完成加工的工序，其优先级为1；依据产品工艺中严密的紧前紧后关系，依次确定工艺树的各层节点及对应的层优先级，因此建立各个节点的层优先级需要操作n次，即确定层优先级的时间复杂度为O(n)。在已经确定了层优先级的节点中查找优先级最高的节点是一个比较简单的过程，其时间复杂度也为O(n)。因此优先级调度策略的总体时间复杂度为O(n)。

(2)在已知工艺树结构的前提下，判断叶节点工序需要操作n次，其算法时间复杂度也为O(n)。对于叶节点工序按照自身加工用时由小到大的排序，所用的时间同样为O(n)。在最坏情况下，复杂产品工艺树为完全多叉树，则查找和排序所用的时间为n2，即时间复杂度为O(n2)。

上述两点的操作次数之和为算法的总时间复杂度，即max{O(n),O(n2)}=O(n2)。

算法框架表述如算法1所示：

算法1考虑层级调度次序的综合调度算法。

DispathProcedure(T);

For each node Wi∈ T do

Set(V)←Compute priority to Wi; /*计算工艺树中各个节点的优先级*/

For each node Vi∈ V do

Set(S)←Highest priority to Vi;/*通过优先级策略确定可最早开始加工的节点*/

For each node Si∈S do

If unique to Si then /*判断优先级最高的节点是否唯一*/

dispath Si;

Else if Leaf Node to Sithen /*叶节点策略*/

dispath Si;

Else

Shortest Time to Si/*通过短用时策略确定加工工时最短的节点*/

dispath Si;

End if

End For

End For

End For

4 Petri网调度设计

作为图形化的系统建模工具，Petri网可以非常直观地描述离散、异步和并发等过程[24]，多用于分布式并发系统的建模与分析。Petri网的建模仿真能够直观地描述系统结构、展现流程情况、模拟系统的运行[25]。早在1990年，庞小红等[26]就将Petri网的相关知识应用于常规调度算法中，后来Petri网在求解制造系统的调度问题中又得到了广泛的应用[27-34]，体现了Petri网较好的建模基础。

本文建模采用基本Petri网[34]，包括4个基本元素，分别是库所(place)、变迁(transition)、有向弧(arc)、令牌(token)。以圆形节点表示库所(place)，对应工序加工设备；以短竖线表示变迁(transition)，对应加工工序；有向弧表示两种偏序关系：由库所指向变迁的关系、由变迁指向库所的关系；通过算法计算令牌(token)值，并根据算法的判断机制更新令牌(token)，调度相应工序。

为便于理解本文算法的思想和优点，现仍以图1所示的实例进行建模仿真。

按照实例分解各工序对应加工设备、紧前紧后关系和加工时间，如表1所示。

表1 产品A加工设备工序表

对应前述调度策略将产品A进行分解：

(1)按照图3所示的产品A工艺图，确定产品A的各个工序的优先级，共有6级，其中工序A11的优先级为6，优先级最高；工序A7、A8、A9、A10的优先级同为5，排在第2位；工序A5、A6的优先级同为4，排在第3位；工序A3、A4的优先级同为3，排在第4位；工序A2的优先级同为5，排在第5位；根节点工序A1的优先级最低，为1；

(2)遍历产品A之后，优先级最高的6级工序只有A11，因此调度A11；

(3)优先级次之的5级工序有4个，因此判断这些工序是否为叶节点；

(4)同为5级的A8、A9、A10均为叶节点，因此根据加工用时较短的原则确定调度工序顺序为A8、A9、A10，至此产品A的调度顺序为A11、A8、A9、A10、A7；

(5)同理确定优先级为4的工序调度顺序为A6、A5；优先级为3的工序调度顺序为A3、A4；

(6)最终确定产品A的调度顺序为A11、A8、A9、A10、A7、A6、A5、A3、A4、A2、A1，具体分解结果如表2所示，调度过程如表3所示。

表2 产品A调度策略分解表

表3 本文算法调度过程

根据上述分析，在Platform Independent Petri Net Editor V4.3上建立复杂产品A的Petri网模型，如图3所示。

在图3的Petri网建模图中，变迁的激发与令牌间的关联条件是：当输入库所拥有令牌时，才能激发变迁。当某个具体变迁触发后，对应的输入库所的令牌将被消耗，并为输出库所产生令牌。在图2与图1的对应关系中，模型中库所P1、P2和P3分别对应复杂产品A调度系统中的设备M1、设备M2和设备M3，变迁T1～T11分别对应工序A1～A11。库所P1对应3个变迁：T10、T7和T2，具体作用是T10的输入库所、T7和T2的输出库所。库所P2对应5个变迁：T11、T9、T5、T4和T1，具体作用是T11的输入库所、T9、T5、T4和T1的输出库所。库所P3对应3个变迁：T8、T6和T3，具体作用是T8的输入库所、T6和T3输出库所。

库所和变迁之间存在以下3种状态：①变迁之间的彼此相互独立的并发状态，不存在任何约束关系，即每个变迁在各自的库所中可以被优先激发，例如变迁T8、T10和T11在t=0时刻同时拥有令牌，分别在库所P3、P1和P2同时被激发;②变迁之间具有紧前紧后约束关系的顺序状态，每一个变迁只有其前序约束变迁激发释放令牌后，才能在对应的库所中拥有令牌，进入激发状态，变迁T1、T2、T3、T4、T5、T6和T7都属于这种状态，例如变迁T3必须在变迁T5消耗后，即t=21时刻才能在库所P3中被允许发生激发并消耗;③变迁之间具有库所约束关系的顺序状态，在这种状态中，一个库所往往对应多个变迁，例如T9与变迁T11，只有变迁T11触发完毕后变迁T9才能在其共同拥有的库所P2中拥有令牌。

仿真调度过程如下：

在t=0时刻，库所P1、P2和P3同时拥有令牌，变迁T10、T11和T8被允许发生激发；在t=4时刻，库所P2中变迁T11消耗完毕、释放令牌，变迁T9拥有令牌，被激发；在t=6时刻，库所P3中变迁T8消耗完毕、释放令牌；在t=8时刻，库所P1中变迁T10消耗完毕、释放令牌，变迁T7拥有令牌，被激发；在t=11时刻，库所P2中变迁T9消耗完毕、释放令牌，库所P3中变迁T6拥有令牌，被激发；在t=14时刻，库所P3中变迁T6消耗完毕、释放令牌，库所P1中变迁T7消耗完毕、释放令牌，库所P2中变迁T5拥有令牌，被激发；在t=21时刻，库所P2中变迁T5消耗完毕、释放令牌，变迁T4拥有令牌，被激发；在t=27时刻，库所P3中变迁T3消耗完毕、释放令牌；在t=29时刻，库所P2中变迁T4消耗完毕、释放令牌，库所P1中变迁T2拥有令牌，被激发；在t=36时刻，库所P1中变迁T2消耗完毕、释放令牌，库所P2中变迁T1拥有令牌，被激发；在t=40时刻，库所P2中变迁T1消耗完毕，至此所有变迁结束活动。

Petri网仿真运行的状态由令牌在库所的分布决定，如图4所示。因为实例中包含11道工序，所以实验中激发参数值设置为Token数量11，库所P1、P2、P3对应的Token值和置信区间近似值分别为3和2，5和7，2和5。在运行过程中当某个具体变迁触发完毕后，依据约束关系的下一个变迁等待发生，且均具有确定的状态和对应的时刻，仿真实验有效。

各库所、变迁的对应关系如表4所示。

表4 Petri网模型各库所与变迁对应关系

5 实例对比分析

下面将本文考虑层级调度次序的综合调度算法，分别与同研究领域的文献[19]的考虑串行工序紧密度的择时算法、文献[20]的拟关键路径算法、文献[21]的考虑后续工序的择时算法和文献[22]的可动态生成具有优先级工序集算法进行对比分析，结果表明本文算法的加工用时更少，算法优化效果更好。

5.1 甘特图与Petri网关联分析

在图2的Petri网建模与图5的甘特图映射关系中，建模结构在具体时刻均对应工序的加工状态。

在t=0时刻，设备M1上，叶节点工序A10作为输入库所P1的变迁拥有令牌被激发；设备M2上，层优先级最高为6的工序A11作为输入库所P2的变迁拥有令牌被激发。设备M3上，同层自身加工用时最短的叶节点工序A8作为输入库所P3的变迁拥有令牌被激发。同为优先级为5的叶节点工序A9虽然优先级高于工序A10，但因为库所P2的变迁在t=4时刻才能释放，所以工序A9需要在A11加工完毕后才可以在设备M2上开始加工。

在t=4时刻，设备M2上，层优先级为6的工序A11加工完毕后释放资源，优先级为5的工序A9才拥有令牌被激发。

因为工序A11为工序A7的紧前工序，所以工序A7在工序A11加工结束后才可以开始加工；又因为库所P1中变迁T7必须在变迁T10消耗后才可以被激发，所以工序A7在t=8时刻在设备M1上开始加工，并在t=15时刻加工完毕。至此，优先级为5的同层工序全部加工完毕。

如上所述，优先级为3的同层工序A3和A4在t=27时刻全部加工完毕；优先级为2的工序A2在t=36时刻加工完毕；优先级为1的工序A1在t=40时刻加工完毕；如图5所示，复杂产品A总体加工用时为40工时。

依据本文算法和Petri网建模中资源先激发后消耗过程，库所P1分别在t=0时刻、t=8时刻和t=29时刻获得资源触发变迁T10、T7和T2，即对应工序A10、A7和A2开始加工，在t=36时刻设备M1完成所有加工任务。库所P2分别在t=0时刻、t=4时刻、t=15时刻、t=21时刻和t=36时刻获得资源触发变迁T11、T9、T5、T4和T1，即对应工序A11、A9、A5、A4和A1开始加工，在t=40时刻设备M2完成所有加工任务。库所P3分别在t=0时刻、t=11时刻和t=21时刻获得资源触发变迁T8、T6和T3，即对应工序A8、A6和A3开始加工，在t=27时刻设备M3完成所有加工任务。因此，复杂产品A的总体加工用时为设备M1、M2、M3的最长加工用时，即40工时。

5.2 五种算法甘特图对比

仍以图1所示的产品A加工工艺图为例，文献[19]和文献[21]的算法具有相同之处，即将复杂产品工艺树结构划分成若干个可以一同调度的工序序列；不同之处则是二者的“择时”思想。文献[19]的考虑串行工序紧密度的择时算法的“择时”思想是依次调度待调度序列总加工用时最小和最早的工序(组)。采用文献[19]的算法将产品A加工工艺图逆置后，工序调度顺序为(A11、A7、A5、A3、A10、A6、A4、A8、A9、A2、A1)，加工甘特图如图6所示，总加工用时为45工时。

文献[20]的拟关键路径法首先计算出所有唯一具有紧前紧后约束关系工序(组)的加工总用时，按总用时从长到短依次调度；然后在已经排列完成的工序(组)中插入不存在紧前或者紧后工序的独立工序，工序调度顺序为(A11、A7、A8、A5、A3、A9、A10、A6、A4、A2、A1)，加工甘特图如图7所示，加工总工时为46工时。

文献[21]的考虑后续工序择时算法采用“排序+择时”的策略，首先根据工序节点的位置，选出只有串行关系的工序(组)，组成排序序列，并按序列路径长度降序依次调度；择时策略是以选择最接近调度目标的方案为主，依次选择已调度工序中后续工序中加工开始时间最早的调度方案，工序调度顺序为(A11、A7、A5、A3、A2、A1、A10、A6、A4、A9、A8)，加工甘特图如图8所示，加工总工时为43工时。

文献[22]的可动态生成具有优先级工序集的算法采用“层优先、短用时、长路径”策略，即优先调度层优先级高的工序，若工序层优先级相同，则优先调度加工用时较短的工序，若加工用时也相同，则优先调度处在长路径上的工序；当上述调度方法出现可调度工序和不可调度工序时，则根据“设备忙”的原则动态调整，工序调度顺序为(A11、A8、A7、A9、A10、A6、A5、A3、A4、A2、A1)，加工甘特图如图9所示，加工总工时为44工时。

本文算法工序调度顺序为(A11、A8、A9、A10、A7、A6、A5、A3、A4、A2、A1)，加工甘特图如图5所示，加工总工时为40工时。4种算法调度结果对比分析如表5所示。

5.3 对比结果分析

由表5可知，本文算法的产品完成加工用时最少，设备利用率最高。本文算法调度结果优于其他四种算法，主要是因为：

表5 五种算法调度结果对比分析

(1)本文算法优先调度对结果有重要影响的长路径工序；在不改变待加工工序紧前和紧后工序的前提下，兼顾同层横向工序，提高了工序并行调度的机率。

(2)文献[19]、文献[20]和文献[21]三种算法都没能充分实现工序间的并行处理，出现了重纵轻横的现象；文献[22]的算法没能充分考虑纵向工序的约束关系，出现了重横轻纵的现象。

文献[19]考虑串行工序紧密度的择时算法，注重使用“择时”的调度策略来确定工序开始加工的时间点，同样没有充分考虑到设备的利用率。在图6中，设备M1在t=19～t=34连续的时间里一直处于空闲状态，设备M3在t=4～t=16的这段时间里也没有加工工序，因而导致了对复杂产品加工过程的整体影响。

文献[20]的拟关键路径法算法，虽然充分考虑了纵向关系工序的调度与最终调度结果之间的决定性关系，却忽略了横向工序的并行性，使设备产生了较多空闲时间段，影响了设备的利用率。

文献[21]的考虑后续工序择时算法，虽然考虑了工序间紧前紧后工序的制约关系，也考虑到了串行和并行工序对调度工序的整体影响，但同样忽略了对空闲设备的充分利用。

在图7和图8的两种算法加工甘特图中，设备M1在t=0～t=4时刻、设备M2在t=4～t=11时刻、设备M3在t=6～t=17时刻的时间内，均产生了不可利用的设备空间。

文献[22]的可动态生产具有优先级工序集的算法，在纵横兼顾的基础上进一步优化了调度算法，但是该算法仍然以纵向调度为主线，降低了具有约束关系的紧前紧后工序之间的衔接度。在图9中，M3在t=7～t=19的12个工时内一直处于空闲状态。

如图5所示，本文算法在t=0～t=4的时间段内设备M1上A10正在加工、设备M2上A11正在加工、设备M3上A8正在加工；在t=4～t=11的时间段内设备M1上A10和A7紧密衔接加工、设备M2上A11和A9紧密衔接加工、设备M3上A8加工完毕后，A6开始加工。并且，在本文算法中工序A6在t=11时刻开始加工，早于其他4种算法的加工开始时间，从而导致了A6后序工序的加工时间也随之提前，进而缩短了产品A的总体用时。

6 结束语

本文针对同层工序数较多的复杂产品综合调度问题，在遵循层优先原则基础上，充分考虑工序自身在复杂产品结构中的位置和加工用时等特性，设计了考虑层级调度次序的资源协同调度算法。在理论阐述分析算法兼顾了产品工艺树中横向工序并行处理力度的基础上，又通过Petri网建模仿真验证了算法较好地利用了设备的空闲时间，提高了设备的整体利用率，从而达到缩短复杂产品总加工用时的优化目的。

本文算法为解决综合调度问题提供了新的方法，扩展了解决问题的思路，有一定理论和实际意义。未来，还可以在以下3方面开展深入研究：①引入更多的优化算法来提高解决综合调度问题的能力；②需要考虑具有特殊约束关系结构的综合调度问题；③多目标综合调度问题。