The analysis of activity networks under generalized precedence relations (GPRs). (English) Zbl 0758.90044

Summary: We present a model for activity networks under generalized precedence relations (GPRs), discuss its temporal analysis and the issues that may arise relative to inconsistency among the specified relations and the activity durations. We also give a more precise definition to the concept of critically of an activity, and introduce the new concept of flexibility of an activity which is akin to the traditional concept of activity floats in regular CPM, with the latter taking on different meaning from its common interpretation in standard CPM.
Issues of optimization are raised when one assumes, for each activity, a piecewise-linear time-cost function that permits positive and negative deviations from its least-cost duration between specified lower and upper bounds on that duration. We seek the optimal activity durations subject to the specified GPRs and a given due date \(\lambda\). We also seek the construction of the complete project duration-cost function between the project minimum duration and its least-cost duration when the due date \(\lambda\) is interpreted, first, as a “deadline” and, second, as a “target date” with rewards for early, and penalties for late completion. The relations between the problems posed and the uncapacitated minimum cost flow problems are revealed and are utilized in the algorithmic solution of the problems.


90B35 Deterministic scheduling theory in operations research
90B10 Deterministic network models in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI