Cost/time trade-off analysis for the critical path method: a derivation of the network flow approach
- PDF / 590,985 Bytes
- 4 Pages / 595 x 842 pts (A4) Page_size
- 42 Downloads / 199 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
Cost/time trade-off analysis for the critical path method: a derivation of the network ¯ow approach BM Baker School of Mathematical and Information Sciences, Coventry University, UK. A well-known problem in critical path analysis involves normal and crash durations being provided for each activity, with corresponding costs, and requires a minimum cost schedule of durations to be determined for all possible durations of the project. It has long been known that an optimal solution to the problem can be obtained iteratively by constructing a minimum cost network ¯ow problem and adjusting the durations of activities corresponding to a minimum capacity cut-set. A recent paper described this method, but gave no indication of how the method could be derived. It is shown here that a linear programming formulation and its dual enables this to be done very simply. Keywords: CPM; networks and graphs; project management
Introduction 1
A recent paper by Phillips considered the following wellknown problem arising in critical path analysis. The activities of a project can be carried out at a normal level or, for certain activities, at a crash level, that is with reduced duration and at increased cost. Intermediate durations for such activities are assumed possible at a pro rata increase in cost. The problem is to determine the durations of individual activities that give rise to minimum total cost for all possible durations of the complete project. The optimising algorithm described by Phillips is essentially the same as that of Kelley.2 The procedure has been described and referred to as Kelley's algorithm by, for example, Fletcher and Clarke.3 Phillips describes his paper as presented for practical application, and gives no justi®cation or explanation for the algorithm. The aims of this note are, ®rstly, to show that a straightforward mathematical programming formulation can be used to justify the method and, secondly, to overcome a minor drawback in Phillips' procedure by a small change. Together with an illustrative example, substantially improved insight and understanding are offered over that given by Phillips. The presentation, interpretation and insights differ suf®ciently from that of Kelley, to offer added interest to both academics and practitioners. Statement of the problem Consider a critical path analysis problem consisting of activities A1 ; . . . ; AN . For each activity, Aj, a normal duration, T1j, and a crash duration, T2j 4 T1j , are given, with Correspondence: Dr BM Baker, School of MIS, Coventry University, Priory Street, Coventry, CV1 5FB, UK.
corresponding costs of g1j and g2j 5 g1j . We calculate a cost-slope for each activity, representing the cost of reducing the activity duration by one time unit, given by: cj
g2j ÿ g1j T1j ÿ T2j
for all j where T2j < T1j ; otherwise cj 1:
Thus, if activity Aj is performed with a duration of tj ; T2j 4 tj 4 T1j , the cost incurred is Gj g1j cj
T1j ÿ tj ; P and the total cost
Data Loading...
