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

聿蒆袈罿莈蒅薈螂芄蒄蚀羇膀薄螂螀肆薃蒂羆羂薂薄螈莀薁螇羄芆薀衿袇膂蕿蕿肂肈薈蚁袅莇薈螃肁芃蚇袆袃腿蚆薅聿肅节蚈袂羁芁袀肇荿芁薀羀芅芀蚂膅膁艿螄羈肇芈袆螁莆莇薆羆节莆蚈蝿膈莅螁羅肄莅薀螈肀莄蚃肃荿莃螅袆芅莂袇肁膁莁薇袄肇蒀虿肀羃葿螂袂芁葿蒁肈膇蒈蚄袁膃蒇螆膆聿蒆袈罿莈蒅薈螂芄蒄蚀羇膀薄螂螀肆薃蒂羆羂薂薄螈莀薁螇羄芆薀衿袇膂蕿蕿肂肈薈蚁袅莇薈螃肁芃蚇袆袃腿蚆薅聿肅节蚈袂羁芁袀肇荿芁薀羀芅芀蚂膅膁艿螄羈肇芈袆螁莆莇薆羆节莆蚈蝿膈莅螁羅肄莅薀螈肀莄蚃肃荿莃螅袆芅莂袇肁膁莁薇袄肇蒀虿肀羃葿螂袂芁葿蒁肈膇蒈蚄袁膃蒇螆膆聿蒆袈罿莈蒅薈螂芄蒄蚀羇膀薄螂螀肆薃蒂羆羂薂薄螈莀薁螇羄芆薀衿袇膂蕿蕿肂肈薈蚁袅莇薈螃肁芃蚇袆袃腿蚆薅聿肅节蚈袂羁蚄芃薀螂蚃羂莃蚈蚂肄薈薄蚂膇莁蒀蚁艿膄蝿螀罿荿蚅蝿肁膂薁螈芃莇薇螇羃芀蒃螆肅蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒂莅袂膄芅蚄袁袄蒁蚀袀肆莃薆袀腿蕿蒂衿芁莂螀袈羀膅蚆袇肃莀薂羆膅膃蒈羅袅莈莄羄羇膁螃羄腿蒇虿羃节艿薅羂羁 编号062262的第二次修改稿。修改说明见第1720页。基于相关任务分配的网络计划的算法 郭 强西北工业大学 理学院 应用数学系 710072 西安摘要 研究如何把具有紧前紧后关系的工作集分配给现有的人员（或设备），使完成工作集的总工期最短，并在此条件下，使得用于所有工作上的时间之和最少。文中揭示了任意改变一项工作的用时或最早开工时间，将引起其他工作的最早开工时间的变化规律，并在此基础上借鉴Floyd算法规则，建立了一种获取该问题最优解的迭代算法。这种算法能保证总工期随迭代过程递减，在总工期达到最短时，能保证总工期不变，而总用时随迭代过程递减。使用这种算法，不用绘制PERT图，只需输入每个人承担不同工作的用时，以及各工作间的紧前紧后关系，即可算出最优分配方案、总工期及各工作的最早开工时间、松弛时间。关键词：分配问题；PERT问题；A-PERT问题； Floyd算法；最早开工时间；松弛时间。An Algorithm of Network planningBased on Dependent Task Allocation Guo QiangDepartment of Applied Mathematics, School of Science , Northwestern Polytechnical University, Xian 710072Abstract: In order to make the total work period shortest and the total spending time of all works least on this condition, this paper studies how assign the works with the precedence and successor relationship to every personnel or equipment. At the same time, it presents the change law of earliest starting time of other works when changing the spending time or the earliest starting time of any work. Based on this, an iterative algorithm is established to obtain the optimal solution of the problem using Floyd algorithm rule. This algorithm can assure that the total work period is descending along with the iterative process, the total spending time is descending along with the iterative process when the total work period is shortest. This algorithm need not draw PERT graph, but only input the works for every personnel and the precedence and successor relationship between every two works, then it will compute the optimal allocation programs, the total construction period, the earliest start time and relaxation time for every work.Keywords: assignment problem; PERT problem; A-PERT problem; Floyd algorithm; earliest starting time; relaxation time1、引言研究如何把具有紧前紧后关系的任务集分配给现有的人员（或设备），在保证完成任务集的总工期最短的前提下，使总用时最少，是一种充分利用现有的人力和物力，最大限度地提高工作效率的优化问题。这样的优化问题，在生产调度、机械加工、以及工程计划制定与管理等活动中，无疑有着重要的应用价值。但是要解决这样的问题，却并不容易，文献1证明了使总工期最短的问题是一个NP-hard问题，不存在多项式时间的算法，在问题规模较大的情况下，很难获得精确最优解。因此，人们对这类问题的研究，普遍着眼于寻找近似最优解或称满意解的算法上，以及如何提高近似最优解的精度和计算效率。如，文献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问题的完整描述如下：某项工程由项工作构成，各工作之间具有已知的紧前、紧后关系，现有个人可参与这项工程。规定每项工作只能由一个人承担。已知第个人完成第项工作需用时。研究：要完成这项工程中的所有工作应如何进行分配，才能够使总工期最短，并在此条件下，使用于所有工作上的时间之和最少，以及在这种要求下的总工期、各项工作的最早开工时间和松弛时间。A-PERT问题涉及到三种情况，统一的要求是每项工作只能由一个人承担，不同的要求是，时，每个人至少承担一项工作；时，每个人只承担一项工作；时，每个人至多承担一项工作。设 用表示按进行分配时，所需总工期。A-PERT问题的数学模型为：其中，为参变量。当时，；当时，。这是一个双层0-1整数规划，虽然可以用穷举法求解，即，计算出所有不同分配方案下的总工期，通过比较，可以选出总工期最短时总用时最少的分配方案（最优解）。但是这样的方法计算量太大，在时，要计算次PERT问题；在时，要计算n！次PERT问题；在时，要计算次PERT问题。所以，在A-PERT问题的规模较大时，这种方法显然是不可行的。本文将针对情况，介绍一种借助Floyd算法规则求解A-PERT问题的算法，至于 和两种情况，可以在此基础上，类似地给出算法。3、A-PERT问题的算法理论从上述A-PERT问题的描述可以看出，在A-PERT问题所给条件下，如果只求总用时最少的分配方案，则涉及的便是经典分配问题；如果给定了分配方案，再求总工期及各项工作的最早开工时间和松弛时间，则涉及的便是经典的计划评审技术问题，又称PERT问题。因此，求解A-PERT问题，可以借鉴文献10中求解经典分配问题的方法：按照一定的规律，反复从一种分配方案变换到另一种总用时更少的分配方案，直到最终获得总用时最少的分配方案。即，按照以下思路解决A-PERT问题：按照一定的规律，反复从一种分配方案变换到另一种总工期更短或总工期不增的情况下总用时更少的分配方案，直到最终获得总工期最短的情况下总用时最少的分配方案。要实现这样的目的，关键是找出上面提到的规律。另外，要使算法具有实用的计算效率，应尽量降低迭代过程中出现的每一种分配方案下的总工期和总用时的计算量。研究表明，再借鉴文献11中求解PERT问题的算法，便可以实现这一目的，达到这样的要求。为此，先给出文献10和文献11中的相关理论。定理1 设为上述问题的一个可行分配方案（表示安排第个人承担第项工作），（为第个人承担第项工作的用时，为第个人承担第项工作的用时，是用于记录人员调整的方法。）。则通过下面两步运算： 若，则；否则都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了一个可减少总用时的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着当前的分配方案已经是总用时最少的分配方案。证 参见文献10。定义1 已知一项工程由个具有紧前、紧后关系的工作构成，第项工作需用时。若第项工作无紧前工作时，则令第0项工作为其紧前工作；若第项工作无紧后工作时，则令第n+1项工作为其紧后工作，。设则称矩阵为初始PERT矩阵，对应的网络称为复线PERT网络。显然，一个初始PERT矩阵对应着一个有向网络，第项工作对应着第个节点（），节点到相邻可达的节点的边长为第项工作的用时。节点不相邻可达节点时，令，是为了便于计算。定义2 若矩阵中的元素表示复线PERT网络中节点到节点的最长路值，则称该矩阵为最优PERT矩阵。定理2 设为初始PERT矩阵，则通过下列运算： 若，则；否则不变。转到。若，则，转到；否则，输出。得到的矩阵是最优PERT矩阵，且有下列结果：（1）第项工作的最早开工时间为；（2）第项工作的最早完工时间为；（3）完成该项工程所需总工期为；（4）第项工作的松弛时间为；（5）第项工作的最迟开工时间为；（6）第项工作的最迟完工时间为。证 参见文献11。定理1给出了一种寻找总用时最少的分配方案的方法，定理2给出了一种在每一项工作的用时都确定的情况下，获取总工期及各项工作最早开工时间和松弛时间的方法。当某一项工作的用时被改变，其它相关工作的最早开工时间是否会发生变化，如何变化，具有以下规律：定理3 设为最优PERT矩阵。若，则改变第项工作的用时，不会影响第项工作的最早开工时间。证 由最优PERT矩阵知，时，意味着第项工作不是第项工作的的后继工作，所以，则改变第项工作的用时，不会影响第项工作的最早开工时间。定理4 设第项工作的最早开工时间为，用时为又设第s项工作是第k项工作的任意一个紧后工作，则当第k项工作的用时改变时，下列结论成立：（1）不存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。（2）存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。证 （1）不存在时，说明第k项工作是其紧后工作的唯一紧前工作，所以第k项工作完成后，第k项工作的紧后工作即可开工，而第k项工作的最早开工时间为，用时为，所以，第k项工作的紧后工作的最早开工时间为。（2）存在时，说明第k项工作不是其紧后工作的唯一紧前工作，所以只有当第项工作的所有紧前工作都完成后，第项工作才能开工，而是第项工作的完工时间最晚的紧前工作的完工时间，所以，第k项工作的紧后工作的最早开工时间为。推论 在定理5的条件下，当第k项工作的最早开工时间改变时，下列结论成立：（1）不存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。（2）存在时，第k项工作的紧后工作的最早开工时间变为，最早开工时间的改变量为。证 与定理5完全类似，略。如果第项工作的最早开工时间改变时，我们引入则根据定理3和定理4及其推论可知，在第项工作的用时改变后，第项工作的所有前期工作的最早开工时间不变，而所有后期工作的最早开工时间可通过下面运算获得： 求 求， 若不存在，则；否则（存在）。 若，则，转到；否则（）直接转到。 若，则转到；否则（），转到。 若，则转到；否则（）转到。 若，则转到；否则（）停。为便于论述，用表示第项工作用时改变后，由上述运算步骤得到的第项工作的最早开工时间，则按Floyd算法规则执行运算，可获得以下运算规律：定理5 设为第人做第项工作的用时，为一个可行分配方案，是对应该分配方案的最优PERT矩阵。表示将第人承担第项工作改为第人承担第项工作后，造成第项工作的用时改变量，表示第项工作用时改变后，第s项工作的最早开工时间，表示第项工作用时改变后，总工期的改变量，再引入人员调换记录，则通过下面两步运算： 若时，则，；否则，都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了一个可缩短总工期的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着当前的分配方案已经是总工期最短的分配方案。证 （1）因为，如果存在一个分配方案：安排第人做第项工作，第人做第项工作， ，第人做第项工作时的总工期比安排第人做第项工作时的总工期短，则是的一个全排列。为了便于论述，不妨设（其它情况证明类似），则用第人替换第1人，第人替换第2人，第人替换第人，总工期便会缩短。因此，以下必有一组按次序执行的运算式成立： 因为，这组按次序执行的运算，都属于定理中的、两步运算的搜索范围，只是执行的是能够成立的一组，又因为运算前，所以执行、的结果是中必有一个小于0，所以，用记录到的调整过程，按定理中的、进行调整，便得到一个总工期更短的分配方案。（2）对（1）的证明已揭示，只要存在比当前分配方案下的总工期更短的分配方案，定理中的、两步运算一定能将其找出来。同时也表明，如果当前的分配方案已经使总工期达到最短了，则在的过程中，按定理中的、两步运算，始终不会出现，所以，始终不变，故，即始终成立。定理6 设分配方案使总工期达到了最短，则通过下面两步运算： 若，且，则，；否则，都不变。转到。 求，当，时，转到可获得以下信息：（1）当时，意味着找到了一个可减少总用时的循环调整方案：记，在时，转到，直到为止。（2）当的过程中，始终，意味着在保持总工期不变的前提下，当前的分配方案已经使总用时到了最少。证 类似于定理5的证明，略。4、A-PERT问题的程序算法上述A-PERT问题的算法理论揭示，求解A-PERT问题， 可以按下面模块化的算法流程图进行：给定初始分配方案：用定理2求该分配方案下的最优PERT矩阵按定理3、定理4及推论：yesnonoyes 用定理5按照记录，调整分配方案：，同时更新每一项工作的最早开工时间： 判断是否存在总工期更短的分配方案 用定理6判断是否存在总工期不变但总用时减少的分配案输出最优分配方案：及每项工作的最早开工时间：，其中为总工期。求解A-PERT问题的精确最优解的具体算法步骤如下： 输入已知数据：， 用最小元素法定初始分配方案：。 用定理2求最优PERT矩阵： 按照定理3和定理4，计算将第项工作改由第人承担后，第项工作的最早开工时间：，对应的总工期的改变量：，记录调整过程：，。 计算逐步增加改变工作承担者的工作后，搜寻使总工期变短或总工期不变时使总用时变少的调整方案：。 若，则，转到；否则转到。 若且，则，转到；否则直接转到。 若，则转到；否则（）转到。 若，则转到；否则（）转到。 判断是否存在缩短总工期的部分作业承担者的循环调整：求若，则，转到；否则（）转到。 判断是否存在减少总用时的部分作业承担者的循环调整：求 若，则，转到；否则（）转到。 调整分配方案：，。 若，则，转到；否则（），转到。 若，则转到；否则，输出到最优分配方案：；及各工作的最早开工时间：。注：（1）如果需要各项工作的松弛时间，可以根据最优分配方案下的各项工作用时，用定理2获得。也可从开始，利用与倒着递推出各项工作的松弛时间。（2）A-PERT问题算法必然在有限次迭代运算中获得精确最优解，其理论依据为定理5和定理6。（3）A-PERT问题的算法，是以缩短总工期或总工期不能再缩短时减少总用时为前提，由一个可行分配方案转换到另一个可行分配方案的迭代算法（对于n个人，n项工作的分配问题，称一人做一项工作，每项工作只由一个人做的分配方案为可行分配方案。）。由于，该问题的所有不同的可行分配方案共有n!种，所以，理论上在最坏情况下，可能要迭代运算n!次才能获得最优分配方案。因此，按迭代次数统计，A-PERT问题算法的复杂度为，属于指数算法。但是，算法的初始可行分配方案，是用最小元素法定出的，而且迭代运算是按总工期递减或总工期不能缩短时按总用时递减进行的，所以，运算中跳过了大量的不能使总工期缩短或总工期达到最短时，不能减少总用时的分配方案下相关计算。因此，如用单纯形法求解线性规划问题那样，A-PERT问题算法虽然属于指数算法，却具有适用的计算效率、和稳定的数值结果，从我们计算过的一些算例也显示，用本文给出的算法求解A-PERT问题，实际迭代次数都远远少于次。如下面一个例子：例 已知某项工程含有8项工作，各工作之间的紧前紧后关系如表3所示 表3工 作紧前工作无无紧后工作无现有8个工作组，每个工作组完成各项工作的用时见表4 表4用时 工作工作组一12161421187119二6911191212107三142116121452313四1515272117191620五913192015161114六23182410871512七1520814176918八12161191015148要求每项工作只能由一个工作组承担，每个工作组只能承担一项工作。研究：如何进行工作分配，使完成该项工程的总工期最短的前提下，所有工作组的用时之和最少，并求出这种要求下各项工作的最早开工时间、最迟开工时间、松弛时间。 解 由算法步骤和算法步骤分别得到初始分配方案和当前各项工作的最早开工时间，见表5。表5工作1工作2工作3工作4工作5工作6工作7工作8工作组25746318最早开工时间0061313342139此时，总工期为47，总用时为80。 通过算法步骤-由一个可行分配方案转换到另一个总工期更短或总工期最短时总用时更少的可行分配方案，共进行11次转换（这远远小于8！次），便得到最优分配方案及最优工程计划下的各项工作的最早开工时间见表6。在此基础上，还可得到最优分配方案下各项工作的松弛时间见表6。表6工作1工作2工作3工作4工作5工作6工作7工作8工作组42786351最早开工时间001599231728松弛时间00050000此时，总工期为37，总用时为74。5、结束语在关键作业上增加人力、物力、技术的投入，可以减少关键作业的用时，并且，在一定程度上能达到缩短总工期，提高生产效率的目的12，但是，值得注意的是，使用这种方法必然要加重成本的投入，更何况并非所有关键作业都能减少用时。另外，不论减少多少关键作业的用时，总工期也不会短于PERT网络的次最长路。因此，当PERT网络的最长路与次最长路相差无几时，通过减少关键作业的用时来缩短总工期，效果是微不足道的。例如，某个工程由9个作业项目构成，这9个作业项目间的紧前紧后关系如图2所示，每条边上的数字，表示对应作业的用时。 46 3 7 （图2） 8 12 10 9不难看出该工程的总工期为20，不论将关键作业（粗箭线对应的作业）的用时如何缩短，新的总工期都不会短于19。本文的研究的A-PERT问题，是一种不额外投入人力、物力和财力的情况下，充分利用现有资源，最大限度地提高生产效率优化问题。所给算法，不但能获得使总工期最短的分配方案，而且能保证总工期最短的情况下，使总用时最少。这种算法有稳定的计算性能和适用的计算效率，可在企业特别是大型企业的生产任务分配与进度计划制定中发挥重要的作用。另外，由于这种算法获得的是精确最优解，所以，可以供各种近似算法进行近似最优解的精确程度比较，这比目前许多文献采用的近似最优解与近似最优解的优劣比较更客观，更能说明问题。参考文献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.1990,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 architectures. IEEE Trans Parallel and Distributed Systems. 1993,4(2):75-875石威、郑纬民，相关任务图的均衡动态关键路径调度算法。计算机学报，2001，24（9）：991-9976尚明生，相关任务图的一种有效并行调度算法。计算机工程，2005,31(14): 18-20，297蒋延耀、李庆华，DAG任务图的一种调度算法。小型微型计算机系统，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): 30831410郭强，分配问题的一种新的迭代算法。系统工程与电子技术，2004,26(12): 1915-1916,194911郭强，PERT问题的新算法。数学的实践与认识，2003,33(2): 48-5112尹建伟、韩伟力、陈刚、董金祥，项目工期调整的公平负担算法。计算机辅助设计与图形学学报，2002,14(3): 270-274作者简介：郭 强，男，汉族，1961年出生，副教授。主要研究方向：最优化理论与算法，运筹与网络规划。已在国内外多种学术期刊上发表论文30余篇。研究背景基于相关任务分配的网络计划问题的算法,是研究下面问题的精确算法： 某项工程由n个具有紧前、紧后关系（已知）的作业构成，现有m个工作组，规定每项作业只能由一个工作组承担。已知第i个工作组完成第j项作业用时需。研究：完成所有作业应如何进行分配，使总工期最短，并在此条件下，使所有作业上的用时之和最少，以及在这种要求下各作业的最早开工时间、松弛时间及总工期。这个问题应用很广泛，但却是一个NP-hard问题，因此，引起许多科技工作者的研究兴趣，近些年来，在中外许多学术刊物上，针对使总工期最短的问题，每年都有相当数量的研究报道，不过所介绍的方法几乎都是近似算法，为了说明自己的算法更优，每篇文献都将自己的算法与其它文献中的算法进行了对比，但是，比较的对象又都是近似算法，因此，其优劣只能是相对的，每一种算法都无法表明其近似最优解的精确程度。出现这种情况的主要原因是，目前缺少求取这类问题的精确最优解的算法。另外，目前所有文献都只研究使总工期最短的问题，而没有涉及使总工期最短的前提下，再使总用时最少的问题。因此，研究求这类问题的精确最优解的算法不但属于新问题，而且有重要的现实意义和理论意义。虽然，本文给出的算法不是多项式时间算法，但是，这种算法始终是按总工期长度递减的方向进行迭代运算的，一旦总工期达到最短时，便能在总工期保持不变的情况下，始终按总用时最少的方向进行迭代运算。因此，在实际应用中，可以减少大量的不同分配情况下的总工期和总用时的计算量，所以，算法不但有适用的计算效率，而且有稳定的计算性能。本文研究的问题及其算法，可在企业特别是大型企业的生产任务分配与进度计划制定中发挥重要的作用。另外，由于这种算法获得的是精确最优解，所以，可以供各种近似算法进行近似最优解的精确程度比较，这比目前许多文献采用的近似最优解与近似最优解的优劣比较更客观，更能说明问题。针对专家的修改意见说明编辑先生：您好！感谢专家提出的二审意见！对照专家的12条修改意见，我对投稿论文进行了仔细的研读和修改。现将所做修改及欲与专家商榷的问题罗列如下：针对专家的修改意见（1），对引言中的引例描述进行了修改，突出了本文要研究的问题是，寻找使总工期最短的情况下，总用时最少的分配方案，而且要研究求其精确最优解的算法。另外，为了避免误会，删除了单纯形法虽然是指数算法，却有实用的计算效率议论。针对专家的修改意见（2），答复：本文研究的问题，是一种特殊的多目标规划问题，确切地说，是一种双层01规划问题，其与一般多目标规划不同的是，内层最优解一般不唯一，是一个集合，外层目标函数的可行域是内层最优解的集合。典型的网络最大流的最小费用问题也属于这类双层规划问题（但不是01规划）。因此，凡具备运筹学基本知识或数学规划基本知识的读者应该不会产生疑义的。另外，考虑到行文的逻辑性，我觉得还是不把A-PERT问题定义提前到引言中为好。不过，为了避免误解，对引言中的问题引出，进行了修改。针对专家的疑问（3），答复：专家认为“从定理中的算法看，应该是有可能的”的理解是错误的。因为在定理2中，最初所以，运算前，因此，通过运算： 若，则，否则（）不变。每个只会随运算变小（至多不变），不会变大。所以，由获得的，不可能有的情况。在定理3中，最初 所以，运算前，因此，通过运算： 若，则，否则（）不变。每一个只会随运算变小（至多不变），不会变大。所以，由获得的，不可能有的情况。因此，专家认为定理2和定理3中，是有可能的，的理解是错误的。 针对专家的疑问（4），答复：对于文中运算的介绍，我原先给得不够清楚，给专家审稿造成了一定的困难。这次我在修改稿中，将原先几个定理的先后次序进行了调整，先通过调整次序后的定理3、定理4及其推论，归纳出了运算定义，然后才在文中运用运算符号，并且在定理中对每一个变量名都补充了说明。相信这次专家再审我的稿件，就不会对文中的运算符产生疑问了。对专家问的原稿“第7-8页中的输入和输出是什么？第8、9步是否多余？”的答复：输入的是已知数据，输出的是运算结果，不知这有何疑问？第8、9步也不是多余的，缺了这两部，只能得到第k项工作的紧后工作的最早开工时间，而得不到其他后继工作的最早开工时间。针对专家的建议（5），答复：在上次修改时，掉了第4节标题，这次已将其补上，并按专家的意见，将A-PERT问题作为单独的一节。针对专家的建议（6），答复：按照专家的建议，在这一稿中我按照模块化的形式补上了A-PERT问题的算法流程图。针对专家的疑问（7），答复：第10页注（2）是没问题的，是完全正确的。专家之所以对此有一连串的疑问，原因是没有完全理解原稿中的定理2和定理3。因为，理解了定理2和定理3，就不会有前面的疑问（3），而疑问（3）解决了，即可看出，稿中针对A-PERT问题的算法，使总工期随迭代运算逐步缩短，在总工期不可再缩短时，使总用时随迭代运算逐步减少。为了使专家和读者能够更好地理解算法的原理，在这次修改中，不但对相关定理中的变量都补充了说明，而且补上了定理的详细证明。专家的第（7）条疑问，可以在本次修改稿中的定理5、定理6及其证明中，得到详细的答复。针对专家的疑问（8），答复：本文给出的A-PERT问题的算法，是以缩短总工期或总工期不能再缩短时减少总用时为前提，由一个可行分配方案转换到另一个可行分配方案的迭代算法（对于n个人，n项工作的分配问题，称一人做一项工作，每项工作只由一个人做的分配方案为可行分配方案。）。由于，该问题的所有不同的可行分配方案共有n!种，所以，理论上在最坏情况下，可能要迭代运算n!次才能获得最优分配方案。不过这样的例子我举不出来，不知专家能否举出，请赐教！从我们运算过的一些例子看，的确是迭代次数远远少于n!时，便获得了最优解，只是原文中“大量的运算结果都显示”有些用词不当，为此，这次将这样的表述做了修改。针对专家的疑问（9），答复：在数学规划研究中，对于迭代算法，通常都是用迭代次数来反映算法的时间复杂度的，为此，上一稿中，已说明本文所给算法的计算复杂度为n!次迭代运算，即O(n!)，不知为何不可？至于专家称“从算法上看似乎是多项式时间复杂度，因此不大可能得到精确最优解”是不对的，本文给出的算法属于指数算法，但得到的一定是精确最优解，其理论依据见本次修改后论文中的定理5和定理6及其证明。针对专家的疑问（10），答复：专家称“用求出精确最优解的方法来评价近似最优解是没有意义的，既然已经求出了精确解，何必还要求近似解？”，对此我有不同的看法。近似算法的产生来源于两点：一是找不到精确算法，不得已而为之；二是为了追求更快的计算速度，而弃用已有的精确算法（尤其是对于指数复杂度的问题）。但不论是哪一种原因，近似算法都会把近似程度作为一个重要的考量。从所查阅到的文献看，对于求解使总工期达到最短的相关任务的分配问题，都是采用近似计算方法，其原因是他们都没有找到精确算法，在这种情况下，将一种近似算法的结果与另一种近似算法的结果进行比较，只能是相对的，而无法说明算法本身所达到的精确程度。专家称“近似最优解的评价一般是参照最优解的上界进行的，而且这样的界可以通过多项式时间求出。”不知依据出自何处？其实，这样的说法是不合适的，因为，数学规划的最优解是一组变量的取值，可视为一个向量，因此，最优解是一个以向量为元素的点集（最优解唯一时，为单点集，不唯一时，为一般点集。），而点集只有有界无界之分，没有上下界之分。如果专家的意思是，最优解一定在可行域（点集）中