A minimum incoming weight label method and its application in CPM networks

Abstract

An effcient approach towards finding a directed, shortest path or a directed longest path from the source to all other nodes in a directed network is described in this paper. Application of this approach with respect to CPM project networks is also considered. The approach is based on a minimum incoming weight labelling method and determines a critical path for a given project activity network. Although many algorithms exist in the operational research literature that may be used to find critical paths, the method discussed in this paper has an interesting application in determining optimal crash limits for various activities in a CPM network. In case of network topology changes due to any reason, such as that an activity has to be completed in crash duration or the actual duration of an activity takes longer than scheduled, a new critical path and new associated floats can be computed without analyzing the complete network all over again. This is achieved by recycling part of the available information. The algorithm presented in this paper is illustrated by means of numerical examples.

Keywords: CPM network, activity crash limit, minimum weight label, shortest path, longest path,
protean system, information recyclin

ORiON Vol. 24 (1) 2008: pp. 37-48