The resource constrained time/cost tradeoff project scheduling problem with discounted cash flows
研究了在资源约束下通过压缩活动时间以最大化项目净现值的调度问题，提出了一种启发式算法，并对比了三种优先规则在380个测试问题上的表现。
Abstract Many of the recent studies on Project Scheduling focus on maximizing the Net Present Value (NPV) of cash flows that occur during the implementation of a project in the presence of precedence and resource constraints. The literature contains several integer programming formulations, heuristic procedures and their implementations. In most of these formulations, activity durations are assumed to be fixed. In this paper, we study a practical extension of the problem where the activity durations can be reduced from their normal durations by allocating more resources. Costs associated with such reductions are referred to as crashing costs. The problem under consideration involves determining the timing and duration of activities such that the NPV of all cash flows is maximized in the presence of precedence and resource constraints. We suggest a heuristic procedure for obtaining “good” feasible solutions. We compare the performance of three priority rules embedded in the proposed procedure. Two of these priority rules have been shown to be the most effective in the literature, the third is a new rule developed in this paper. Extensive computational experiments with the heuristic procedure on a total of 380 test problems are reported. The heuristic solutions are compared to benchmark solutions obtained from the best of 50‐randomly generated solutions for each test problem. In addition, upper bounds on the optimal values are obtained by performing Subgradient optimization on a Lagrangian Relaxation of the problem. These upper bounds are used to assess the quality of the heuristic solutions. In general, none of the priority rules produced consistently better results for all the test problems. However, all three priority rules provide “good” quality solutions with modest computational effort. The Lagrangian approach is found to provide tight bounds on the optimal values.