Chinese Journal of Computers   Full Text
Title	An Algorithm of Network Plan Based on Dependent Task Assignment
Authors	GUO Qiang
Address	(Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an 710072)
Year	2008
Issue	No.7(1138—1146)
Abstract &   Background	Abstract 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. Keywords assignment problem; PERT problem; A-PERT problem; Floyd algorithm; earliest starting time; relaxation time Background The problem of network plan based on the assignment of dependent tasks is the integration and generalization of assignment problem and PERT problem (Program Evaluation and Review Technique), and belong to operational research field. The problem generally is described as follow: The engineering consists of n 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 m( Such problem has important application in production planning and human resources management for modern enterprises, especially large enterprises. Almost studies at home and abroad are on finding the assignment plan of shortest engineering period in the circumstances m=n. But they do not involve that further reduce the total time of all the tasks when the engineering period is shortest. It is well known such assignment problem is the NP-hard problem. Therefore, the existing research results are through the use of the approximate algorithm. According to the case of m=n, this paper gives a precise algorithm, which not only the shortest engineering period can be solved, but also ensure the total time of all the tasks least when the engineering period is shortest. Although this method is not polynomial time algorithm, the iterative operations of this algorithm have always been in the direction of shortening the engineering period. When the shortest engineering period is achieved, the algorithm will ensure that the iterative operations are always in the direction of decreasing the total time, and remaining the shortest engineering period not be changed. Therefore, the algorithm has applicable and stable computing performance. The precise algorithm have not been found for the problem that m