Minimizing total waiting time in CPM using network flows

In CPM, once an assignment of duration to activities has been determined, there is still flexibility in terms of timing the events. More precisely, the starting (or ending) time of any activity which is not on one of the critical paths from origin to the output vertex is not uniquely determined. The extra time available from the time point an activity is completed to the start of succeeding event is called floating time (or float) on that activity. If the float of an activity is zero, the activity becomes a critical activity. The goal is to find duration for the activities and consistent time for the events so that the total waiting times minimized. For this purpose, we define parallel paths in acyclic network and certain problem called balancing problem. Then, using network flows, minimization of total waiting time problem can be transformed into a balancing problem on an acyclic network

کلیدواژه ها:

network flows ، CPM ، Minimum waiting time