An Optimal Algorithm for the Resource Constrained Project Scheduling Problem.
STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
The report presents an algorithm for solving a form of the resource constrained project scheduling problem. This particular form of the problem differs from that usually considered in that the time needed to complete a job depends on the amount of resources applied to that job. Jobs are preemptable and the objective is to minimize the project duration. It is shown that this problem is equivalent to the problem of finding that transportation polytope, defined by the resource constraints, of minimal dimension which has a face specified by the precedence constraints. A theorem is presented which gives conditions under which a face of a specified type exists. Using this theorem, the problem transforms into an integer programming problem with variables representing the completion times for each job. The constraint set is defined by inequalities involving addition and maximum operations on the variables and, without the constraint that the variables be integer, the constraint set forms a nonconvex, polyhedral set.
- Administration and Management
- Operations Research