Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
472949 | Computers & Operations Research | 2015 | 6 Pages |
•We consider a stochastic time-cost tradeoff problem.•We present a dynamic programming (DP) formulation for the adaptive threshold policy.•We show that the policy is optimal for a serial-graph project.•We develop a heuristic for arbitrary-graph projects.•We verify through the computational experiments that the heuristic is better than the previous heuristics.
We consider a stochastic time-cost tradeoff problem that determines how much to crash activities with the purpose of minimizing the expected summation of crashing and tardiness costs. We propose a threshold policy that makes a crashing decision contingent on a project׳s current status; crashing an activity to compensate delayed starting time from a predetermined threshold. First, we present a dynamic programming (DP) formulation to find the threshold values, and prove that the resulting threshold policy is optimal for a serial-graph project. Since the above optimality does not hold generally, we develop a DP-based procedure to construct a threshold policy for arbitrary-graph projects.We show through the computational experiments that our threshold policy is rapidly constructed by this procedure, and its cost is not very far from the theoretical lower bound.