基于相关任务分配的网络计划的算法

1、基于相关任务分配的网络计划的算法 郭 强西北工业大学 理学院 应用数学系 西安710072 摘要 研究如何把具有紧前紧后关系的工作集分配给现有的人员（或设备），使完成工作集的总工期最短，并在此条件下，使得用于所有工作上的时间之和最少。文中揭示了任意改变一项工作的用时或最早开工时间，将引起其他工作的最早开工时间的变化规律，并在此基础上借鉴Floyd算法规则，建立了一种获取该问题最优解的迭代算法。这种算法能保证总工期随迭代过程递减，在总工期达到最短时，能保证总工期不变，而总用时随迭代过程递减。使用这种算法，不用绘制PERT图，只需输入每个人承担不同工作的用时，以及各工作间的紧前紧后关系，即可算出最

2、优分配方案、总工期及各项工作的最早开工时间和松弛时间。关键词：分配问题；PERT问题；A-PERT问题； Floyd算法；最早开工时间；松弛时间。An Algorithm of Network planBased on Dependent Task Assignment Guo QiangDepartment of Applied Mathematics, School of Science , Northwestern Polytechnical University, Xian 710072Abstract: How assigning the jobs with precedence a

3、nd successor relationship to every person (or facility) so that the engineering period is the shortest, and in this premise the total time of completing all the jobs in the engineering is the least is studied in this paper. Through reveal the changed law of the earliest start time of all other jobs

4、when the time of any job or its earliest start time is altered, an iterative algorithm is established to obtain the optimal solution in virtue of Floyd algorithm. The algorithm can ensure that the engineering period is shortened with iteration and the total time is decreased with iteration when the

5、engineering period is the shortest. The algorithm is convenient rather than drawing the PERT figure, only the time of every person doing different jobs and the sequential order of all the jobs are inputted, the optimal assignment solution, the shortest engineering period and the earliest start time

6、and relaxation time of every job can be obtained.Keywords: assignment problem; PERT problem; A-PERT problem; Floyd algorithm; earliest starting time; relaxation time1、引言研究如何把具有紧前紧后关系的任务集分配给现有的人员（或设备），在保证完成任务集的总工期最短的前提下，使总用时最少，是一种充分利用现有的人力和物力，最大限度地提高工作效率的优化问题。这样的优化问题，在生产调度、机械加工、以及工程计划制定与管理等活动中，无疑有着重要

7、的应用价值。但是要解决这样的问题，却并不容易，文献1证明了使总工期最短的问题是一个NP-hard问题，不存在多项式时间的算法，在问题规模较大的情况下，很难获得精确最优解。因此，人们对这类问题的研究，普遍着眼于寻找近似最优解或称满意解的算法上，以及如何提高近似最优解的精度和计算效率。如，文献2 给出了一种MCP近似算法，文献3 给出了一种ETF近似算法，文献4 给出了一种DLS近似算法，文献5总结分析了文献2和3，给出了一种BDCP近似算法，文献6和7又在上述近似算法的基础上，给出了新的近似算法。文献8和文献9 则给出了不同的遗传算法。研究这类问题的近似算法的文献还有很多，但是，却很难找到研究这

8、类问题的精确最优解的文献。另外，目前对这类问题的研究都集中在如何获取最短的总工期的问题上，而没有注意到使总工期最短的分配方案通常会有多种，而且，使总工期达到最短的不同分配方案的总用时往往不同，甚至有较大的差异，举一个简单例子：某项工程由三项工作构成，各工作间的紧前、紧后关系如图1。 工作1 工作2 （图1） 工作3已知三个人承担这三项工作的用时情况见表1。 表1用时（周） 工作 人工作1工作2工作3甲838乙2711丙8913通过穷举，可以得到所有分配方案下的总用时与总工期，见表2。 表2工作1工作2工作3总工期总用时方案1（用时）甲 8乙 7丙 131528方案2（用时）甲 8丙 9乙 11

9、1728方案3（用时）乙 2甲 3丙 131318方案4（用时） 乙 2 丙 9 甲 81119方案5（用时） 丙 8 甲 3 乙 111122方案6（用时） 丙 8 乙 7 甲 81523从表2中可看出，按第4、第5套方案进行分配，总工期最短，为11周，但是，第4套分配方案的总用时为19周，比第5套分配方案的总用时22周要少花费3周时间，因此，选择第4套分配方案，不但能使总工期达到最短，而且可以使总用时相对较少。为此，本文提出了一种如何寻找相关任务的分配方案，使总工期达到最短的情况下，使总用时最少的问题，本文将这种问题称为A-PERT问题。无疑，这是一个新的、有意义的现实问题。2、A-PER

10、T问题的特征及其数学模型A-PERT问题的完整描述如下：某项工程由项工作构成，各工作之间具有已知的紧前、紧后关系，现有个人可参与这项工程。规定每项工作只能由一个人承担。已知第个人完成第项工作需用时。研究：要完成这项工程中的所有工作应如何进行分配，才能够使总工期最短，并在此条件下，使用于所有工作上的时间之和最少，以及在这种要求下的总工期、各项工作的最早开工时间和松弛时间。A-PERT问题涉及到三种情况，统一的要求是每项工作只能由一个人承担，不同的要求是，时，每个人至少承担一项工作；时，每个人只承担一项工作；时，每个人至多承担一项工作。设 用表示按进行分配时，所需总工期。A-PERT问题的数学模型

11、为：其中，为参变量。当时，；当时，。这是一个双层0-1整数规划，虽然可以用穷举法求解，即，计算出所有不同分配方案下的总工期，通过比较，可以选出总工期最短时总用时最少的分配方案（最优解）。但是这样的方法计算量太大，在时，要计算次PERT问题；在时，要计算n！次PERT问题；在时，要计算次PERT问题。所以，在A-PERT问题的规模较大时，这种方法显然是不可行的。本文将针对情况，介绍一种借助Floyd算法规则求解A-PERT问题的精确算法，以此为基础，有利于进一步研究和两种情况下的A-PERT问题。3、A-PERT问题的算法理论从上述A-PERT问题的描述可以看出，在A-PERT问题所给条件下，如

12、果只求总用时最少的分配方案，则涉及的便是经典分配问题；如果给定了分配方案，再求总工期及各项工作的最早开工时间和松弛时间，则涉及的便是经典的计划评审技术问题，又称PERT问题。因此，求解A-PERT问题，可以借鉴文献10中求解经典分配问题的方法：按照一定的规律，反复从一种分配方案变换到另一种总用时更少的分配方案，直到最终获得总用时最少的分配方案。即，按照以下思路解决A-PERT问题：按照一定的规律，反复从一种分配方案变换到另一种总工期更短或总工期不增的情况下总用时更少的分配方案，直到最终获得总工期最短的情况下总用时最少的分配方案。要实现这样的目的，关键是找出上面提到的规律。另外，要使算法具有实用

13、的计算效率，应尽量降低迭代过程中出现的每一种分配方案下的总工期和总用时的计算量。研究表明，再借鉴文献11中求解PERT问题的算法，便可以实现这一目的，达到这样的要求。为此，先给出文献10和文献11中的相关理论。定理1 设为上述问题的一个可行分配方案（表示安排第个人承担第项工作），（为第个人承担第项工作的用时，为第个人承担第项工作的用时，是用于记录人员调整的方法。）。则通过下面两步运算： 若，则；否则都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了一个可减少总用时的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着当前的分配方案已经是总用时最少的分配方

14、案。证 参见文献10。定义1 已知一项工程由个具有紧前、紧后关系的工作构成，第项工作需用时。若第项工作无紧前工作时，则令第0项工作为其紧前工作；若第项工作无紧后工作时，则令第n+1项工作为其紧后工作，。设则称矩阵为初始PERT矩阵，对应的网络称为复线PERT网络。显然，一个初始PERT矩阵对应着一个有向网络，第项工作对应着第个节点（），节点到相邻可达的节点的边长为第项工作的用时。节点不相邻可达节点时，令，是为了便于计算。定义2 若矩阵中的元素表示复线PERT网络中节点到节点的最长路值，则称该矩阵为最优PERT矩阵。定理2 设为初始PERT矩阵，则通过下列运算： 若，则；否则不变。转到。若，则，

15、转到；否则，输出。得到的矩阵是最优PERT矩阵，且有下列结果：（1）第项工作的最早开工时间为；（2）第项工作的最早完工时间为；（3）完成该项工程所需总工期为；（4）第项工作的松弛时间为；（5）第项工作的最迟开工时间为；（6）第项工作的最迟完工时间为。证 参见文献11。定理1给出了一种寻找总用时最少的分配方案的方法，定理2给出了一种在每一项工作的用时都确定的情况下，获取总工期及各项工作最早开工时间和松弛时间的方法。当某一项工作的用时被改变，其它相关工作的最早开工时间是否会发生变化，如何变化，具有以下规律：定理3 设为最优PERT矩阵。若，则改变第项工作的用时，不会影响第项工作的最早开工时间。证

16、由最优PERT矩阵知，时，意味着第项工作不是第项工作的的后继工作，所以，则改变第项工作的用时，不会影响第项工作的最早开工时间。定理4 设第项工作的最早开工时间为，用时为又设第s项工作是第k项工作的任意一个紧后工作，则当第k项工作的用时改变时，下列结论成立：（1）不存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。（2）存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。证 （1）不存在时，说明第k项工作是其紧后工作的唯一紧前工作，所以第k项工作完成后，第k项工作的紧后工作即可开工，而第k项工作的最早开工时间为，用时为，所以，第k项工作的紧后工作的最早开

17、工时间为。（2）存在时，说明第k项工作不是其紧后工作的唯一紧前工作，所以只有当第项工作的所有紧前工作都完成后，第项工作才能开工，而是第项工作的完工时间最晚的紧前工作的完工时间，所以，第k项工作的紧后工作的最早开工时间为。推论 在定理5的条件下，当第k项工作的最早开工时间改变时，下列结论成立：（1）不存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。（2）存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。证 与定理5完全类似，略。如果第项工作的最早开工时间改变时，我们引入则根据定理3和定理4及其推论可知，在第项工作的用时改变后，第项工作的所有前期工作的

18、最早开工时间不变，而所有后期工作的最早开工时间可通过下面运算获得： 求 求， 若不存在，则；否则（存在）。 若，则，转到；否则（）直接转到。 若，则转到；否则（），转到。 若，则转到；否则（）转到。 若，则转到；否则（）停。为便于论述，用表示第项工作用时改变后，由上述运算步骤得到的第项工作的最早开工时间，则按Floyd算法规则执行运算，可获得以下运算规律：定理5 设为第人做第项工作的用时，为一个可行分配方案，是对应该分配方案的最优PERT矩阵。表示将第人承担第项工作改为第人承担第项工作后，造成第项工作的用时改变量，表示第项工作用时改变后，第s项工作的最早开工时间，表示第项工作用时改变后，总工期

19、的改变量，再引入人员调换记录，则通过下面两步运算： 若时，则，；否则，都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了一个可缩短总工期的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着当前的分配方案已经是总工期最短的分配方案。证 （1）因为，如果存在一个分配方案：安排第人做第项工作，第人做第项工作， ，第人做第项工作时的总工期比安排第人做第项工作时的总工期短，则是的一个全排列。为了便于论述，不妨设（其它情况证明类似），则用第人替换第1人，第人替换第2人，第人替换第人，总工期便会缩短。因此，以下必有一组按次序执行的运算式成立： 因为，这组按次序执行的

20、运算，都属于定理中的、两步运算的搜索范围，只是执行的是能够成立的一组，又因为运算前，所以执行、的结果是中必有一个小于0，所以，用记录到的调整过程，按定理中的、进行调整，便得到一个总工期更短的分配方案。（2）对（1）的证明已揭示，只要存在比当前分配方案下的总工期更短的分配方案，定理中的、两步运算一定能将其找出来。同时也表明，如果当前的分配方案已经使总工期达到最短了，则在的过程中，按定理中的、两步运算，始终不会出现，所以，始终不变，故，即始终成立。定理6 设分配方案使总工期达到了最短，则通过下面两步运算： 若，且，则，；否则，都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了

21、一个可减少总用时的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着在保持总工期不变的前提下，当前的分配方案已经使总用时到了最少。证 类似于定理5的证明，略。4、A-PERT问题的程序算法上述A-PERT问题的算法理论揭示，求解A-PERT问题， 可以按下面模块化的算法流程图进行：给定初始分配方案：用定理2求该分配方案下的最优PERT矩阵按定理3、定理4及推论：yesnonoyes 用定理5按照记录，调整分配方案：，同时更新每一项工作的最早开工时间： 判断是否存在总工期更短的分配方案 用定理6判断是否存在总工期不变但总用时减少的分配案输出最优分配方案：及每项工作的最早开工时

22、间：，其中为总工期。求解A-PERT问题的精确最优解的具体算法步骤如下： 输入已知数据：， 用最小元素法定初始分配方案：。 用定理2求最优PERT矩阵： 按照定理3和定理4，计算将第项工作改由第人承担后，第项工作的最早开工时间：，对应的总工期的改变量：，记录调整过程：，。 计算逐步增加改变工作承担者的工作后，搜寻使总工期变短或总工期不变时使总用时变少的调整方案：。 若，则，转到；否则转到。 若且，则，转到；否则直接转到。 若，则转到；否则（）转到。 若，则转到；否则（）转到。 判断是否存在缩短总工期的部分作业承担者的循环调整：求若，则，转到；否则（）转到。 判断是否存在减少总用时的部分作业承担

23、者的循环调整：求 若，则，转到；否则（）转到。 调整分配方案：，。 若，则，转到；否则（），转到。 若，则转到；否则，输出到最优分配方案：；及各工作的最早开工时间：。注：（1）如果需要各项工作的松弛时间，可以根据最优分配方案下的各项工作用时，用定理2获得。也可从开始，利用与倒着递推出各项工作的松弛时间。（2）A-PERT问题算法必然在有限次迭代运算中获得精确最优解，其理论依据为定理5和定理6。（3）A-PERT问题的算法，是以缩短总工期或总工期不能再缩短时减少总用时为前提，由一个可行分配方案转换到另一个可行分配方案的迭代算法（对于n个人，n项工作的分配问题，称一人做一项工作，每项工作只由一个人

24、做的分配方案为可行分配方案。）。由于，该问题的所有不同的可行分配方案共有n!种，所以，理论上在最坏情况下，可能要迭代运算n!次才能获得最优分配方案。因此，按迭代次数统计，A-PERT问题算法的复杂度为，属于指数算法。但是，算法的初始可行分配方案，是用最小元素法定出的，而且迭代运算是按总工期递减或总工期不能缩短时按总用时递减进行的，所以，运算中跳过了大量的不能使总工期缩短或总工期达到最短时，不能减少总用时的分配方案下相关计算。因此，如用单纯形法求解线性规划问题那样，A-PERT问题算法虽然属于指数算法，却具有适用的计算效率、和稳定的数值结果，从我们计算过的一些算例也显示，用本文给出的算法求解A-

25、PERT问题，实际迭代次数都远远少于次。如下面一个例子：例 已知某项工程含有8项工作，各工作之间的紧前紧后关系如表3所示 表3工 作紧前工作无无紧后工作无现有8个工作组，每个工作组完成各项工作的用时见表4 表4用时 工作工作组一12161421187119二6911191212107三142116121452313四1515272117191620五913192015161114六23182410871512七1520814176918八12161191015148要求每项工作只能由一个工作组承担，每个工作组只能承担一项工作。研究：如何进行工作分配，使完成该项工程的总工期最短的前提下，所有工作

26、组的用时之和最少，并求出这种要求下各项工作的最早开工时间、最迟开工时间、松弛时间。 解 由算法步骤和算法步骤分别得到初始分配方案和当前各项工作的最早开工时间，见表5。表5工作1工作2工作3工作4工作5工作6工作7工作8工作组25746318最早开工时间0061313342139此时，总工期为47，总用时为80。 通过算法步骤-由一个可行分配方案转换到另一个总工期更短或总工期最短时总用时更少的可行分配方案，共进行11次转换（这远远小于8！次），便得到最优分配方案及最优工程计划下的各项工作的最早开工时间见表6。在此基础上，还可得到最优分配方案下各项工作的松弛时间见表6。表6工作1工作2工作3工作4

27、工作5工作6工作7工作8工作组42786351最早开工时间001599231728松弛时间00050000此时，总工期为37，总用时为74。5、结束语在关键作业上增加人力、物力、技术的投入，可以减少关键作业的用时，并且，在一定程度上能达到缩短总工期，提高生产效率的目的12，但是，值得注意的是，使用这种方法必然要加重成本的投入，更何况并非所有关键作业都能减少用时。另外，不论减少多少关键作业的用时，总工期也不会短于PERT网络的次最长路。因此，当PERT网络的最长路与次最长路相差无几时，通过减少关键作业的用时来缩短总工期，效果是微不足道的。例如，某个工程由9个作业项目构成，这9个作业项目间的紧前紧

28、后关系如图2所示，每条边上的数字，表示对应作业的用时。 46 3 7 （图2） 8 12 10 9不难看出该工程的总工期为20，不论将关键作业（粗箭线对应的作业）的用时如何缩短，新的总工期都不会短于19。本文的研究的A-PERT问题，是一种不额外投入人力、物力和财力的情况下，充分利用现有资源，最大限度地提高生产效率优化问题。所给算法，不但能获得使总工期最短的分配方案，而且能保证总工期最短的情况下，使总用时最少。这种算法有稳定的计算性能和适用的计算效率，可在企业特别是大型企业的生产任务分配与进度计划制定中发挥重要的作用。另外，由于这种算法获得的是精确最优解，所以，可以供各种近似算法进行近似最优解

29、的精确程度比较，这比目前许多文献采用的近似最优解与近似最优解的优劣比较更客观，更能说明问题。参考文献1Garey M.R., Johnson Ds., Computers and Intractability-A Guide to the Theory of NP-Completeness, New York: Freeman W.H.and Co. 19792Wu M Y,Gajski D D,Hypertool.A programming aid formessage-passing systems.IEEE Trans Parallel and Distributed Systems.1

30、990,1(3):330-3433Hwang J J, chow Y C, Anger F D,Lee C Y. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal on Computing.1989,18(2):244-2574Sih G C and Lee E A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor arch

31、itectures. IEEE Trans Parallel and Distributed Systems. 1993,4(2):75-875石威、郑纬民，相关任务图的均衡动态关键路径调度算法。计算机学报，2001，24（9）：991-997 SHI Wei ，ZHENG Wei-Min. The Balanced Dynamic Critical Path Scheduling Algorithm of Dependent Task Graphs. Chinese Journal of computers. 2001，24（9）：991-9976尚明生，相关任务图的一种有效并行调度算法。计

32、算机工程，2005,31(14): 18-20，29 SHANG Ming-sheng. Efficient Algorithm for Scheduling Dependent Task Graphs on Multi-processor System. Computer Engineering. 2005,31(14): 18-20，297蒋延耀、李庆华，DAG任务图的一种调度算法。小型微型计算机系统，2003，24（10）：1796-1799 JIANG Ting-yao; LI Qing-hua. A Scheduling Algorithm for DAG Task Graphs.J

33、ournal of Chinese Computer Systems. 2003，24（10）：1796-17998 Kwok Yu-Kwong, Ishfaq Ahumad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. Journal of Parallel and Distributed Computing, 1997,47(1): 58-779钟求喜、谢涛、陈火旺，任务分配与调度的共进化方法。计算机学报，2001,24(3): 30

34、8314 ZHONG Qiu-xi, XIE Tao, CHEN Huo-wang. Task Allocation & Scheduling by Computational Model of Coevolution. Chinese Journal of computers. 2001,24(3): 30831410郭强，分配问题的一种新的迭代算法。系统工程与电子技术，2004,26(12): 1915-1916,1949 GUO Qiang. New iterative algorithm for an assignment problem. Systems Engineerin

35、g and Electronics. 2004,26(12): 1915-1916,194911郭强，PERT问题的新算法。数学的实践与认识，2003,33(2): 48-51 GUO Qiang. A New Algorithm of PERT. Mathematics in Practice and theory. 2003,33(2): 48-5112尹建伟、韩伟力、陈刚、董金祥，项目工期调整的公平负担算法。计算机辅助设计与图形学学报，2002,14(3): 270-274 YIN Jian-wei,HAN Wei-li,CHEN Gang,DONG Jin-xiang. Fair Al

36、gorithm of Goal-Driven Time Limit Modification for a Project. Journal of Computer-Aided design & Computer Graphics. 2002,14(3): 270-274 作者简介：郭 强，男，汉族，1961年4月出生，理学硕士，副教授。主要研究方向：最优化理论与算法，运筹与网络规划。 Guo Qiang, born in 1961, associate professor, Master of Science. His research interests include the th

37、eory and algorithm of optimization, operational research and mathematics programming in network.E-mail: guoqiang研究背景 基于相关任务分配的网络计划问题属于运筹学领域，是分配问题和计划评审技术问题的综合与推广，其一般性描述为： 某工程由项具有紧前、紧后关系的工作构成，现要安排个人去完成这项工作。规定每项工作只能由一个人承担，每个人至少承担一项工作。已知第个人完成第项工作业需用时。要研究的问题是：如何进行人与工作之间的分配，使得完成该项工程的总工期最短，并在此条件下，使得用于所有工作的

38、用时之和最少，并给出这种要求下，各项工作的最早开工时间和松弛时间。这样的问题在现代企业，特别是现代大型企业的生产计划制定和管理中有着重要的运用。目前国内外对这种问题，都是在的情况下，研究如何寻找使总工期最短的分配方案。由于这是一个NP-hard问题，因此，现有的研究成果，采用的都是近似算法，而且也没有涉及到使总工期最短的前提下，再使总用时最少的问题。与此不同是，本文针对的情况，给出了使总工期达到最短的前提下，又使总用时最少的精确算法。虽然，这种算法不是多项式时间算法，但是，这种算法始终是按总工期长度递减的方向进行迭代运算的，一旦总工期达到最短时，便能在总工期保持不变的情况下，始终按总用时最少的

39、方向进行迭代运算。因此，该算法有适用的计算效率和稳定的计算性能。对于的情况下，如何寻找上述问题的精确算法，这一问题我们还未解决。但是，我们已研究出了的情况下，项工作无紧前紧后关系时，获取使总工期最短，及在此前提下，使总用时最少的精确算法，其将另文给出。BackgroundThe problem of network plan based on the assignment of dependent tasks is the integration and generalization of assignment problem and PERT problem (Program Evaluat

40、ion and Review Technique) ，and belong to operational research field. The problem generally is described as follow: the engineering consists of tasks with precedence and successor relationship. Each task can only be taken by one person, and every person must take at least one task when persons are as

41、signed to complete those tasks. Let is the time that th person takes to complete th task. The objective of the research is how assigning those jobs to every person so that the engineering period is the shortest, and in this premise the total time of completing all those jobs is the least. Finally the algorithm must give the earliest start time and relaxation time for each task. Such problem has important app