A New Formulation of the Resource-Unconstrained Project Scheduling Problem with Generalized Precedence Relations to Minimize the Completion Time

摘要

It is known that the resource-unconstrained project scheduling problem with generalized precedence constraints (RUPSP) and minimum completion time objective function can be solved in time O(n · m), where n is the number of activities and m is the number of precedence relations. In this article, we propose a new network formulation for RUPSP based on a transformation that maps the original problem into a standardized acyclic network where precedence relationships between each pair of activities are only of the finish-to-start type with zero time lags. With this network, we then associate a mathematical program that can be solved in O(m) time by means of dynamic programing. Exploiting the dual formulation of this mathematical program we further prove that the minimum completion time can also be computed, with the same computational complexity O(m), by finding an augmenting path of longest length in the proposed acyclic network by installing unit capacities on arcs. Computational results on benchmarks are presented.