A New Polynomial Algorithm for Total Tardiness Minimization of the Sequencing Optimal Problem of Parallel Activities

The problem of M activities of NM > parallel activities being adjusted to a procedure chain is one type of the project scheduling. In allusion to 3 M = , a new polynomial algorithm is proposed to minimize the total tardiness criterion. In order to present this algorithm, and search the optimal procedure chain, we propose a Normal Chain Theory by virtue of the relationships of activities' time parameters, together with the properties that the optimal chain contains the activities with the minimum of earliest finish time. By the analysis of this algorithm, we get the time complexity is (l og ) ON N.