A FULLY POLYNOMIAL TIME APPROXIMATION SCHEME FOR TWO PROJECT SCHEDULING PROBLEMS

In the paper the resource constrained project scheduling problem is considered. Two fully polynomial time approximation schemes (FPTAS) are constructed for the problem with bounded width of the partial order in two cases that are NP-hard in the strong sense. The time complexity of the FPTAS for the problem to minimize the project completion time is O(2KKM(N2/ɛ)K) operations. Here K is the width of the partial order, and ɛ is an accuracy of the obtained solution. For the problem to minimize the average job completion time, an FPTAS with the running time O(2KKM(N3/ɛ)K) has been proposed. As a corollary, there is an FPTAS for the job shop scheduling problem with a bounded number of jobs.