An Algorithm to Obtain Possibly Critical Paths in Imprecise Project Networks

We consider criticality in project networks having imprecise activity duration times. It is well known that finding all possibly critical paths of an imprecise project network is an NP-hard problem. Here, based on a method for finding critical paths of crisp networks by using only the forward recursion of critical path method, for the first time an algorithm is proposed which can find all possibly critical paths of interval-valued project networks. The proposed algorithm considers interactivity among paths which has not been yet considered in the fuzzy project scheduling literature. The extension of the proposed algorithm to the fuzzy network calculates criticality degrees of activities and paths of projects without any need to enumerate all project paths. Although algorithms for calculating criticality degrees in fuzzy networks have been previously proposed, despite the fact that they mostly consider a specific type of fuzzy numbers as activity duration times, the exiting algorithms do not discriminate possibly critical paths before calculating the criticality degrees. The computational experience on a series of well-known project samples confirms the algorithm to be remarkably more efficient than similar algorithms for fuzzy networks.