一种面向定点输出的分布式制造调度算法∗

张祥甫

（海军装备部驻连云港地区军代室 连云港 222061）

1 引言

目前，随着全球一体化的发展以及区域经济格局的形成，一件产品的生产已不再由传统的局部设备生产，而是许多分布式生产单元进行协同制造。其中以局部区域加工能力为主传的传统制造业模式，已逐步被以物流运输为中心的分布式制造所代替。从而导致了现代化的制造业向分布式产业转型。因此，需要好的调度算法对分布式设备进行协调，从而对产品的生产进行全局优化。由于传统的车间调度问题仅将调度算法局限在一个相对较小的车间内，其较少地考虑了产品的运输及分布协同问题。因此，近十年来，学者们开始对分布式制造进行调度优化研究。

然而，分布式调度过程中的另一项关键因素在于对输出点的选择，即任务在何处加工完毕。分布式产品的最终完成位置是分布式调度需要考虑的现实问题，其具有较强的实际意义。例如，在分布调度中以特定的位置作为出口点，分布式生产的过程即围绕着出口点进行任务分配。对此，需要在调度优化过程中考虑加工设备与出口点的距离，以及加工任务的结构特点与分布式设备选择的关联。对此，本文所研究的内容在于，在分布式调度过程中指定输出设备，即固定输出设备约束，并分别根据设备网络的物理距离分布与任务结构分析，建立任务调度的优化方案。对此本文提出了RSM 算法，该方法不仅可以解决，分布设备的定点输出约束，还建立了任务结构度量及设备分布状态度量，从而为工序与设备的分配提供量化指标的同时，综合表达了任务与设备分配的合理性。

2 相关工作

生产调度问题是实际工业生产中的一个重要问题，早在七十多年前就已受到学者们的广泛关注和研究。根据建模，该问题可以表述为满足一系列连续约束和离散约束条件下的目标优化问题［1］。目前，即使是较小规模的生产调度问题，也很难得到最优解随着市场需求的变化和生产设备的改进，同一种类型的设备可以实现多种类型工序的加工，这使得工序不再与设备绑定，而是可以在某个设备集合中选择设备进行加工。为了满足这种调度要求，Bruker 等进一步提出了柔性作业调度（Flexible Job Shop Scheduling Problem，FJSP）［2］。作为传统生产调度问题的一种扩展，柔性作业调度也是NP 困难。为了得到这两类问题的最优解和近似最优解，研究者们提出了大量的启发式算法，其中最著名的算法是由Watson等提出的禁忌搜索算法［3］，近年来人们在此基础上提出了一系列的改进算法［4～6］。此外，研究者们还将遗传算法［7～8］，蚁群算法［9］，粒子群算法［10］，Petri网模型［11］等算法成功应用到生产调度问题和柔性作为调度问题求解中。

近年来，学者们对多目标FJSP 进行了大量的研究。文献［12］以最大完工成时间（Makespan）、加工成本和提前拖期惩罚值为优化目标，建立了相应的优化模型，针对该问题，提出了一种多目标粒子群算法，最后以实例对所建模型及算法进行了验证；文献［13］以Makespan、机器总负载及机器最大负载为目标，提出了一种基于Pareto 优化的离散自由搜索算法，并通过两个实例验证了算法的有效性；文献［14］以Makespan 及设备最大负载为目标，将生产能力约束考虑到约束条件，对问题进行建模，提出了一种改进的遗传算法，最后以标准算例对模型及算法进行了验证；文献［15］以Makespan、设备总负载和设备最大负载为目标，提出了一种基于粒子群算法和局部搜索算法的混合智能算法，并以实例对该算法进行了验证；文献［16］以Makespan、设备总负载和设备最大负载为目标，通过对各优化目标赋予相应的权重，将多个优化目标合并成单一优化目标，从而实现调度优化。

车间调度问题一直是制造领域中的一个研究热点和难点，是实现生产运作与管理的核心，在很大程度上影响着企业的生存和发展。作业车间调度问题（Job Shop Scheduling Problem，JSP）是一种典型的车间调度问题，绝大多数JSP问题均具有NP难特性。元启发式算法为JSP 问题的求解提供了一种有效可行的方案，这些算法虽无法保证达到全局最优解，但通常能在可行的时间内得到问题的近似解，其中包括模拟退火算法、遗传算法、免疫算法以及粒子群算法等等。文献［17］将一种并行模拟退火算法应用于求解JSP 问题，给出了有效的邻域搜索规则。文献［18］提出了一种基于遗传算法和模拟退火算法的混合算法求解以最小化最大完工时间为目标的JSP 问题。文献［19］针对零等待时间的作业车间调度问题，设计了一种混合型遗传算法。文献［8］将局部搜索算法和遗传算法相结合用于求解机器调整时间与工序顺序相关的作业车间调度问题。文献［20］针对以总权重拖期时间为目标的作业车间调度问题，设计了一种免疫退火算法。文献［21］研究了具备路径柔性特征的作业车间调度问题，提出了一种混合型算法求解JSP 问题，利用基于人工免疫算法进行求解。

本文不同与以上算法，本文的创新之处在于利用了分布式设备的运输特性，在考虑设备柔性加工能力的同时，考虑设备的运输关系。对此，本文不仅需要考虑任务的结构特性以及设备的加工能力，还需要考虑设备间的运输关系，此外，对于指定出口节点问题，还需要考虑终止加工的设备的约束。因此，本文所研究问题的复杂性相对于传统算法较高，且具有较好的实用性。对此本文提出了RSM算法，其贡献为：分别建立了任务结构度量及设备分布状态度量，其中任务结构度量反映了后续工序对备选工序的影响，设备分布状态度量反映了设备在设备网络中的局部影响力。从而为工序与设备的分配提供量化指标的同时，综合表达了任务与设备分配的合理性。

3 数学描述说明

分布式系统任务以分片的形式进行调度且各工序之间满足以下约束，即DAG约束：

1）分布式任务具有唯一的终止工序（DAG 出口节点）；

2）分布式设备具有唯一的终止设备，即终止工序需要在终止设备表上完成加工；

3）某一工序仅在满足其要求的设备中执行，且可满足同一工序要求的设备不唯一，工序在各设备中的执行时间已知；

4）任一设备在同一时刻只能执行一个工序；

5）若vj为vi的紧后工序，则vj需要在vi执行完毕后等待vi向vj运输。若vi与vj在同一设备中执行则运输时间为0；

6）每一工序必须在其紧前工序均执行完毕，并收集到所有前序工序运输来的原料时才可开始执行；

7）设备呈离散分布状态，设备间的运输时间受设备通路状态影响；

8）任务具有指定的终止设备，即终止工序必须在终止设备上完成加工。

DAG调度模型的符号描述如下：

1）V=｛v1，v2，……｝表示任务的工序集合，其中|V|为工序的个数；

2）M=｛m1，m2，……｝表示设备的集合，其中|M|表示分布式环境中设备的个数；

3）U 表示运输时间矩阵，ui，j表示设备mi到设备mj的运输时间，若设备mi到设备mj间存在一条最短路｛mi，mi'，mi''，…，mj'，mj｝，则ui，j=ui，i'+ui'，i''+…+uj'，j；

4）r（v）表示v 紧前工序，若vi，vj为vk的紧前工序，即r（vk）=｛vi，vj｝，则vk必须在vi，vj加工完毕且收集到所有前序工序运输来的原料时才可开始执行；

5）e（v）表示分配给工序v的设备；

6）加工矩阵A 表示，Ai，j表示任务vi在设备mj上加工所需要的时间，Ai表示工序v 在所有设备上的加工时间构成的向量。

图1为某一任务的DAG结构，其中节点表示工序，节点v8为终止工序，有向边表示工序的有序关系。表1 为工序在各设备中的执行时间，列举了各工序在8 个设备m1-8上的执行时间。表2 为设备间运输时间矩阵U。图2 为各设备m1-8的分布状态，其权值代表相邻设备的运输时间，m7为终止设备。

表1 图1中工序在各设备上的执行时间

表2 设备间运输时间矩阵U

图1 任务结构模型

图2 设备分布状态

定点输出的调度优化算法的目标是，最小化加工时间。为实现这一目标，需要建立合理的任务分配策略，对此，本文提出了定点输出调度算法。

4 逆向分配调度算法

4.1 逆向分配适应策略

分布式制造调度问题是一类NP 问题，在有限时间内没有最优的分配方案。对此，本文所设计的逆向分配适应策略。其调度原则即在进行设备分配时，以任务的后续设备占用状态及设备分布状态作为指导。其调度过程如下：

1）将终止工序分配到终止设备上，并将止工序的紧前工序作为备选工序，并由备选工序构成的集合即为备选工序集合。例如v8是终止工序，m7为终止设备，则v8需要在m7上加工，则任务v6和v7即为v8分配后的备选工序集B，即B=｛v6，v7｝；

2）若某一任务v 已分配至设备m，即e（v）=m，则v的紧前工序r（v）需要以e（v）与e（v）直接相邻的设备作为备选设备。例如v8是终止工序，m7为终止设 备，即e（v8）=m7，则r（v8）=｛v6，v7｝。此 时，｛m7，m6，m3｝即为工序v6和v7的备选设备集E，即E（v6）=E（v7）=｛m7，m6，m3｝；

3）计算各备选工序v 与其备选设备m 的优先度Ov，m，对于优先度Ov，m最小的一对v 与m，将工序v分配到设备m上加工。Ov，m的表达式如下：

其中pi为工序v 基于任务结构的加工时间权重向量，qj为设备mj基于设备分布状态的加工时间权重，Oi，j为特定v，m 的优先度。其中pi表达了工序的前续工序的加工时间向量。qj是设备的分布状态的权重，表达了设备运输环境中对任务后续调度的贡献度，q 越大其环境贡献度越高。因此，式（1）中，Oi，j越小表示将工序vi分配到设备mj的合理性越强。

4）重复上述过程，直到所有的工序分配完毕。上述过程的重点在于p与q模型的建立，对此，本文在后继部分分别对p模型与q模型的构建过程进行了描述。

4.2 任务结构度量

任务结构度量的目标是根据工序在任务中的分布状态及设备依赖度，对后续调度过程中各工序对设备的依赖度进行估计。若工序vj是工序vi的前续工序，按逆向分配适应策略，vj的设备分配需要等待vi分配设备结束。因此，若vj与vi的距离越远，则vj的设备依赖性对vi设备分配决策的影响越小。对此，本文设计了如下的任务结构度量，以度量工序vi及其后续调度过程的设备依赖度。

其中foreword（vi）表示工序vi的前续工序集合，dis（vi，vj）表示工序vi与工序vi在任务结构图中的最小距离，α为控制参数，Aj表示加工矩阵A 的第j 行，即工序vj在各设备上加工所需要的时间。例如当v8分配到m7设备时，工序v6和v7变为可调度工序。对于工序v6，其前续工序为v2，v4，v1，v3其与v6的距离分别为1，1，2，2。因此，在v6进行调度决策时，需要考虑v6，v2，v4，v1，v3的设备依赖性，根据式（2），当时，p6=1×A6+0.5×A2+0.5×A4+0.33×A1+0.33×A3=［17.8，20.6，16.9，19.3，20.1，21.9，20.6］。此时对于工序v7，根据式（2），p7=1×A7+0.5×A5+0.33×A3=［19.3，11.2，7.5，15.6，10.3，19.6，12.1］。

4.3 设备分布状态度量

设备分布状态度量是根据局部区域内设备对各工序的加工时间及各设备间的运输时间，建立以特定设备为中心的局部区域加工能力度量。对于图2 当v8分配到m7设备后，工序v6和v7变为可调度工序，此时v6与v7可选择的设备为m6，m3，m7，其中m3的相邻设备为｛m1，m5，m6，m7｝，m6的相邻设备为｛m3，m4，m7｝，m7的相邻设备为｛m3，m6｝，m3较于m6和m7具有较好的运输环境，可为后续任务提供更为丰富的设备选择方案，从而减小设备的竞争。对此本文利用数据场模型设计了如下的设备分布状态度量，该模型可度量设备局部区域运输环境中对任务的后续适应度，即为设备的权重。

其中uk，i为设备mk与mi之间的运输时间，σ为距离控制参数，Rk和Ri分别为B 中工序在设备mk与设备mi上加工的等待时间。该模型表达了设备mi所处位置相对于工序加工的重要程度，式（3）中若mi与其他设备的运输时间越短且与mi邻近的设备越多时，qi的取值越大即设备的权重越高。

5 实验分析

5.1 实验环境介绍

为验证CESM 算法的有效性，本文实验部分利用Workflow Generator 生成实验数据，以模拟分布式系统的DAG 任务结构。硬件：intel i3 处理器，4G内存。在对比算法方面，本文将调度问题中的HEFT［22］，CEFT［23］，DCP［24］算法作为对比算法。由于各个算法没有考虑定点输出的问题，因此，需要对以下算法进行定点输出改进：

由于缺少对定点输出调度问题的调度算法

1）HEFT算法，改进方法利用HEFT的rank进行逆向调度，即从终止节点向开始节点方向进行调度。在rank计算过程中，以相邻设备的运输时间均值作为运输作为输入，以rank作为工序选择的优先性；

2）CEFT 算法，改进方法从终止节点开始逆向计算关键路径长度，并以该关键路径长度对任务结果进行逆向拆分；

3）DCP 算法，以工序的最晚开始时间，最早结束时间和作为工序选择设备的优先性，并从任务的终止工序开始，进行逆向调度。

5.2 调度总时间分析

本实验将数据分为Set1，Set2，Set3，Set4 共4个数据集，每个数据集包含100 个‘任务-设备对’。各数据集的生成参数如表3所示。

表3 任务-设备的生成参数表

表4 6种设备集

由于‘各任务-设备对’的总时间差异较大，因此，本文将4个利用如下的score模型对各算法的总时间进行归一化度量：

其中timei（n）表示，算法i 在第n 个‘任务-设备对’上的加工时间，max｛time（n）｝表示各算法对第n 个‘任务-设备对’上加工时间的最大值，scorei表示算法i在100个‘任务-设备对’上的累计得分，若score越低说明算法的加工时间相对越小。例如利用RSM，HEFT，CEFT，DCP对于‘任务-设备对’的调度总时间分别为：20，25，15，10，则各算法对该‘任务-设备对’的得分分别为20/25，25/25，15/25，10/25，即0.8，1，0.6，0.2。图3 为算法在Set1～5 上的scores 分布，其中RSM 的score 取值相对于其他3 个算法最低，说明RSM的总体调度时间最低。

图3 各算法在Set1～5上的scores分布

5.3 设备依赖性分析

设备依赖性是算法对不同设备的选择倾向。为分析各算法的设备依赖性，本实验利用设备占用率作为度量方法，其中占用率（occupancy rate）的表达式如下：

其中o（mj）表示设备mj被占用的时间，|M|为设备总数。若某算法在某一类设备上的占用率越高，说明该算法对该设备依赖性越强。若算法的均衡负载性能越好，则设备的占用率相对越均匀。本次实验设计了5 种设备Machine1～5，每种设备6 个共30 个设备，各设备加工工序的平均时间分别为5，10，15，20，25。以相邻设备的平均运输时间为10 设备网络密度为0.25，随机生成100个含有该30设备的网络。以任务链接密度为0.3，工序个数为100 为参数，随机生成100 个任务。利用RSM，HEFT，CEFT，DCP分别将100个任务在100个设备网络上进行调度，并计算5 种设备的平均占用率。图4 为4 种算法运行结果的设备占用率直方图。从图10的对比可知，HEFT，CEFT，DCP 算法在Machine1～3的占用率明显高于其他设备，且从Machine1 到Machine5 的占用率呈下降趋势，说明HEFT，PCH，HHDS算法均依赖于高效设备。RSM算法在5个设备上的利用率相对均匀，说明RSM 算法具有更好的设备均衡负载的性能，能充分利用低效设备，从而降低了总执行时间。

图4 各算法的设备占用率

5.4 设备均衡性分析

本实验是针对不同的设备集分析RSM 算法的执行效率。实验过程为：1）生成数据D500：500 个任务，每个任务包含的工序数为150，工序的平均加工时间为10，任务链接密度为0.2；2）设备集中的设备分为3 种类型（高效型设备平均加工时间为10，一般型设备平均加工时间为20，低效型设备平均加工时间为30），设备网络的密度为0.25，相邻设备的平均运输时间为10。本实验所设计的6 个设备集如表7 所示，其中每个设备集包含9 个设备。例如设备集Set1 中包含：2 个高效设备，4 个一般设备和3 个低效设备；3）利用4 种算法对每组任务进行调度，并记录每组数据中D500 的500 个任务在6个设备集中的执行时间分布。图4 为4 种算法在6个设备集中的500 个任务执行时间分布散点图，其中从MSet1到MSet6设备集的工作效率逐渐降低，4种算法的任务执行时间分布随之逐渐变高。图5中RSM 在MSet1 和MSet2 设备集中的表现明显优于其他3 种算法，而RSM 在MSet5 和MSet6 中的表现与其他3 种算法接近，其原因在于：在MSet1 和MSet2 中3 种设备的分布较平均，此时考虑均衡负载的RSM 算法优势明显，而在MSet5和Set6中设备类型趋于一致，此时RSM 算法与其他3种算法的表现接近。

图5 500个任务在6个设备集中执行时间散点图

6 结语

本文利用分布式制造系统中设备的分布状态及运输关系，针对任务的定点输出问题，设计了一种逆向分配调度算法RSM。该算法创新思想在于：根据任务结构及设备网络的分布状态，分别建立了任务结构度量p 及设备分布状态度量q，其中任务结构度量反映了后续工序对备选工序的影响，设备分布状态度量q 反映了设备在设备网络中的局部影响力。所建立备选工序与备选设备的量化度量，可以为任务调度提供依据，简化了调度过程，并考虑了任务与设备结构两方面优化。

本文利用了实验验证的方式分析了算法的参数取值，其论证过程及原理说明可作为调度算法的一般性论证方法。通过实验分析验证了本文算法相对于其他面向运算代价优化的调度算法（如HEFT，CEFT，DCP 算）具有更高的有效性。本文分别从调度总时间分析、设备依赖性分析、设备集分析三个方面展开实验，验证了本文RSM 算法的有效性。在实验过程中，由于RSM 从总体出发考虑了任务与设备结构两方面优化，使得RSM 在处理定点输出任务调度问题时的表现突出。

RSM的缺点在于，其调度过程依赖于量化的任务结构度量p 及设备分布状态度量q，因此，其调度结果依赖于p 与q 的参数取值，然而对于不同的数据无法精确确定有效的参数取值，因此，本文的后续工作是对模型参数的取值研究。此外，RSM本质上属于模糊调度，因此，RSM 具有模糊调度的一般缺点，即在任务的工序数量较大时RSM 的优势较明显，而工序数量较少时，RSM的性能波动较大。