Article ID: | iaor19982179 |
Country: | Netherlands |
Volume: | 88 |
Issue: | 1 |
Start Page Number: | 50 |
End Page Number: | 68 |
Publication Date: | Jan 1996 |
Journal: | European Journal of Operational Research |
Authors: | Elmaghraby Salah E., Herroelen Willy S., Demeulemeester Erik L. |
Keywords: | programming: dynamic, programming: branch and bound, networks: scheduling |
We describe two algorithms, based on dynamic programming logic, for optimally solving the discrete time/cost trade-off problem in deterministic activity-on-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single nonrenewable resource committed to it. The first algorithm is based on a procedure proposed by Bein, Kamburowski and Stallmann for finding the minimal number of reductions necessary to transform a general network to a series–parallel network. The second algorithm minimizes the estimated number of possibilities that need to be considered during the solution procedure. Both procedures have been programmed in C and tested on a large set of representative networks to give a good indication of their performance, and indicate the circumstances in which either algorithm performs best.