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

1基于相关任务分配的网络计划的算法郭强西北工业大学理学院应用数学系西安710072摘要研究如何把具有紧前紧后关系的工作集分配给现有的人员（或设备），使完成工作集的总工期最短，并在此条件下，使得用于所有工作上的时间之和最少。文中揭示了任意改变一项工作的用时或最早开工时间，将引起其他工作的最早开工时间的变化规律，并在此基础上借鉴Floyd算法规则，建立了一种获取该问题最优解的迭代算法。这种算法能保证总工期随迭代过程递减，在总工期达到最短时，能保证总工期不变，而总用时随迭代过程递减。使用这种算法，不用绘制PERT图，只需输入每个人承担不同工作的用时，以及各工作间的紧前紧后关系，即可算出最优分配方案、总工期及各项工作的最早开工时间和松弛时间。关键词：分配问题；PERT问题；A-PERT问题；Floyd算法；最早开工时间；松弛时间。AnAlgorithmofNetworkplanBasedonDependentTaskAssignmentGuoQiangDepartmentofAppliedMathematics,SchoolofScience,NorthwesternPolytechnicalUniversity,Xi’an710072Abstract:Howassigningthejobswithprecedenceandsuccessorrelationshiptoeveryperson(orfacility)sothattheengineeringperiodistheshortest,andinthispremisethetotaltimeofcompletingallthejobsintheengineeringistheleastisstudiedinthispaper.Throughrevealthechangedlawoftheearlieststarttimeofallotherjobswhenthetimeofanyjoboritsearlieststarttimeisaltered,aniterativealgorithmisestablishedtoobtaintheoptimalsolutioninvirtueofFloydalgorithm.Thealgorithmcanensurethattheengineeringperiodisshortenedwithiterationandthetotaltimeisdecreasedwithiterationwhentheengineeringperiodistheshortest.ThealgorithmisconvenientratherthandrawingthePERTfigure,onlythetimeofeverypersondoingdifferentjobsandthesequentialorderofallthejobsareinputted,theoptimalassignmentsolution,theshortestengineeringperiodandtheearlieststarttimeandrelaxationtimeofeveryjobcanbeobtained.Keywords:assignmentproblem;PERTproblem;A-PERTproblem;Floydalgorithm;earlieststartingtime;relaxationtime1、引言研究如何把具有紧前紧后关系的任务集分配给现有的人员（或设备），在保证完成任务集的总工期最短的前提下，使总用时最少，是一种充分利用现有的人力和物力，最大限度地提高工作效率的优化问题。这样的优化问题，在生产调度、机械加工、以及工程计划制定与管理等活动中，无疑有着重要的应用价值。但是要解决这样的问题，却并不容易，文献[1]证明了使总工期最短的问题是一个NP-hard问题，不存在多项式时间的算法，在问题规模较大的情况下，很难获得精确最优解。因此，人们对这类问题的研究，普遍着眼于寻找近似最2优解或称满意解的算法上，以及如何提高近似最优解的精度和计算效率。如，文献[2]给出了一种MCP近似算法，文献[3]给出了一种ETF近似算法，文献[4]给出了一种DLS近似算法，文献[5]总结分析了文献[2]和[3]，给出了一种BDCP近似算法，文献[6]和[7]又在上述近似算法的基础上，给出了新的近似算法。文献[8]和文献[9]则给出了不同的遗传算法。研究这类问题的近似算法的文献还有很多，但是，却很难找到研究这类问题的精确最优解的文献。另外，目前对这类问题的研究都集中在如何获取最短的总工期的问题上，而没有注意到使总工期最短的分配方案通常会有多种，而且，使总工期达到最短的不同分配方案的总用时往往不同，甚至有较大的差异，举一个简单例子：某项工程由三项工作构成，各工作间的紧前、紧后关系如图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乙111728方案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-PERT问题的特征及其数学模型A-PERT问题的完整描述如下：某项工程由n项工作构成，各工作之间具有已知的紧前、紧后关系，现有m个人可参与这项工程。规定每项工作只能由一个人承担。已知第i个人完成第j项工作需用时),,2,1;,,2,1(njmiCij。研究：要完成这项工程中的所有工作应如何进行分配，才能够使总工期最短，并在此条件下，使用于所有工作上的时间之和最少，以及在这种要求3下的总工期、各项工作的最早开工时间和松弛时间。A-PERT问题涉及到nmnmnm,,三种情况，统一的要求是每项工作只能由一个人承担，不同的要求是，nm时，每个人至少承担一项工作；nm时，每个人只承担一项工作；nm时，每个人至多承担一项工作。设否则，项工作时人承担第当第0,1jixij),,2,1;,,2,1(njmi用])[(nmijijxCf表示按),,2,1;,,2,1(njmixij进行分配时，所需总工期。A-PERT问题的数学模型为：),,2,1;,,2,1(,1,0),,2,1(,1),,2,1(,])[(min..min1111njmixnjxmixxCftsxCijmiijnjijnmijijminjijij其中，,为参变量。当nm时，1,1mn；当nm时，1,0。这是一个双层0-1整数规划，虽然可以用穷举法求解，即，计算出所有不同分配方案下的总工期，通过比较，可以选出总工期最短时总用时最少的分配方案（最优解）。但是这样的方法计算量太大，在nm时，要计算mnCm!次PERT问题；在nm时，要计算n！次PERT问题；在nm时，要计算nmCn!次PERT问题。所以，在A-PERT问题的规模较大时，这种方法显然是不可行的。本文将针对nm情况，介绍一种借助Floyd算法规则求解A-PERT问题的精确算法，以此为基础，有利于进一步研究nm和nm两种情况下的A-PERT问题。3、A-PERT问题的算法理论从上述A-PERT问题的描述可以看出，在A-PERT问题所给条件下，如果只求总用时最少的分配方案，则涉及的便是经典分配问题；如果给定了分配方案，再求总工期及各项工作的最早开工时间和松弛时间，则涉及的便是经典的计划评审技术问题，又称PERT问题。因此，求解A-PERT问题，可以借鉴文献[10]中求解经典分配问题的方法：按照一定的规律，反复从一种分配方案变换到另一种总用时更少的分配方案，直到最终获得总用时最少的分配方案。即，按照以下思路解决A-PERT问题：按照一定的规律，反复从一种分配方案变换到另一种总工期更短或总工期不增的情况下总用时更少的分配方案，直到最终获得总工期最短的情况下总用时最少的分配方案。要实现这样的目的，关键是找出上面提到的规律。另外，要使算法具有实用的计算效率，应尽量降低迭代过程中出现的每一种分配方案下的总工期和总用时的计算量。研究表明，再借鉴文献[11]中求解PERT问题的算法，便可以实现这一目的，达到这样的要求。为此，4先给出文献[10]和文献[11]中的相关理论。定理1设),,2,1(,,2,1)(niniR为上述问题的一个可行分配方案（表示安排第i个人承担第)(iR项工作），),,2,1,(,)()(njijpCCijiiRijRij（)(iiRC为第i个人承担第)(iR项工作的用时，)(ijRC为第j个人承担第)(iR项工作的用时，ijp是用于记录人员调整的方法。）。则通过下面两步运算：1若ijkjik，则ikijkjikijpp,；否则ijijijkjikp与)(都不变。),,2,1,(nji转到2。2求niii1min，当0，nk时，1kk转到1可获得以下信息：（1）当0时，意味着找到了一个可减少总用时的循环调整方案：记uu，uu0①)()(,)(,00uRvRvRwpvuu②在uv时，vuwuR00,)(，转到①，直到uv为止。（2）当nk,,2,1的过程中，始终0，意味着当前的分配方案已经是总用时最少的分配方案。证参见文献[10]。定义1已知一项工程由n个具有紧前、紧后关系的工作构成，第i项工作需用时),,2,1(niti。若第ni,,2,1项工作无紧前工作时，则令第0项工作为其紧前工作；若第nj,,2,1项工作无紧后工作时，则令第n+1项工作为其紧后工作，010ntt。设)1,,1,0,(,0,njijiijtdiij否则，时。当项工作的紧后工作时项工作是第当第则称矩阵)2()2()(nnijd为初始PERT矩阵，对应的网络称为复线PERT网络。显然，一个初始PERT矩阵对应着一个有向网络，第i项工作对应着第i个节点（1,,1,0ni），节点i到相邻可达的节点j的边长为第i项工作的用时it。节点i不相邻可达节点j时，令ijd，)1,,1,0,(nji是为了便于计算。定义2若矩阵)2()2()(nnijd中的元素)1,,1,0,(njidij表示复线PERT网络中5节点i到节点j的最长路值，则称该矩阵为最优PERT矩阵。定理2设)2()2()(nnijd为初始PERT矩阵，则通过下列运算：10k2若ijkjikddd，则kjikijddd；否则ijijkjikdddd)(不变。)1,,1,0,(nji转到3。3若1nk，则1kk，转到2；否则)1(nk，输出)2()2()(nnijd。得到的矩阵)2()2()(nnijd是最优PERT矩阵，且有下列结果：（1）第j项工作的最早开工时间为),,2,1(njdoj；（2）第j项工作的最早完工时间为),,2,1(njtdjoj；（3）完成该项工程所需总工期为