Article ID: | iaor2003928 |
Country: | United Kingdom |
Volume: | 53 |
Issue: | 7 |
Start Page Number: | 741 |
End Page Number: | 751 |
Publication Date: | Jul 2002 |
Journal: | Journal of the Operational Research Society |
Authors: | Demeulemeester E., Herroelen W., Vanhoucke M. |
Keywords: | scheduling, programming: branch and bound |
The discrete time/cost trade-off problem assumes the duration of project activities to be discrete, non-increasing functions of the amount of a single non-renewable resource. The problem has been studied under three possible objectives. The so-called deadline problem involves the scheduling of project activities in order to minimize the total cost of the project while meeting a given deadline. The budget problem aims at minimizing the project duration without exceeding a given budget. A third objective involves the generation of the complete efficient time/cost profile over the set of feasible project durations. In this paper we describe a solution procedure for the deadline problem in which three special cases of time-switch constraints are involved. These constraints impose a specified starting time on the project activities and force them to be inactive during specified time periods. We propose a branch-and-bound algorithm and a heuristic procedure which both make use of a lower bound calculation for the discrete time/cost trade-off problem (without time-switch constraints). The procedures have been coded in Visual C++, version 6.0 under Windows 2000 and have been validated on a randomly generated problem set. We also discuss an illustrative example based on a real-life situation.