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

研究如何把具有紧前紧后关系的工作集分配给现有的人员(或设备),使完成工作集的总工期最短,并在此条件下,使得用于所有工作上的时间之和最少.文中揭示了任意改变一项工作的用时或最早开工时间引起其它工作的最早开工时间的变化规律,并在此基础上借鉴Floyd算法规则,建立了一种获取该问题最优解的迭代算法.这种算法能保证总工期随迭代过程递减,在总工期达到最短时,能保证总工期不变,而总用时随迭代过程递减.使用这种算法,不用绘制PERT图,只需输入每个人承担不同工作的用时以及各工作间的紧前紧后关系,即可算出最优分配方案、总工期及各项工作的最早开工时间和松弛时间.

An Algorithm of Network Plan Based on Dependent Task Assignment

This paper studies how assigning the jobs with precedence and 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.Through reveal the changed law of the earliest start time of all other jobs 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 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 and relaxation time of every job can be obtained.