An adaptive crashing policy for stochastic time-cost tradeoff problems

• Published in: Computers & operations research 2015-11, Vol.63, p.1-6
• Main Authors: Kang, Changmuk, Choi, Byung-Cheon
• Format: Article
• Language: English
• Subjects: Adaptive policy; Breakdowns; Construction costs; Cost reduction; Costs; Crashes; Decision making models; Dynamic programming; Operations research; Optimization; Policies; Stochastic models; Stochastic project scheduling; Stochasticity; Studies; Thresholds; Tradeoff analysis
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2015.04.021

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