An adaptive crashing policy for stochastic time-cost tradeoff problems

• 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.