A Stochastic Branch-and-Bound Approach to Activity Crashing in Project Management
- 1 May 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 12 (2), 125-135
- https://doi.org/10.1287/ijoc.12.2.125.11894
Abstract
Many applications such as project scheduling, workflow modeling, or business process re-engineering incorporate the common idea that a product, task, or service consisting of interdependent time-related activities should be produced or performed within given time limits. In real-life applications, certain measures like the use of additional manpower, the assignment of highly-skilled personnel to specific jobs, or the substitution of equipment are often considered as means of increasing the probability of meeting a due date and thus avoiding penalty costs. This paper investigates the problem of selecting, from a set of possible measures of this kind, the combination of measures that is the most cost-efficient. Assuming stochastic activity durations, the computation of the optimal combination of measures may be very expensive in terms of runtime. In this article, we introduce a powerful stochastic optimization approach to determine a set of efficient measures that crash selected activities in a stochastic activity network. Our approach modifies the conventional Stochastic Branch-and-Bound, using a heuristic—instead of exact methods—to solve the deterministic subproblem. This modification spares computational time and by doing so provides an appropriate method for solving various related applications of combinatorial stochastic optimization. A comparative computational study shows that our approach not only outperforms standard techniques but also definitely improves conventional Stochastic Branch-and-Bound.Keywords
This publication has 9 references indexed in Scilit:
- Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-boundEuropean Journal of Operational Research, 1999
- On Optimal Allocation of Indivisibles Under UncertaintyOperations Research, 1998
- A branch and bound method for stochastic global optimizationMathematical Programming, 1998
- Scheduling projects to maximize net present value — the case of time-dependent, contingent cash flowsEuropean Journal of Operational Research, 1997
- Net-present-value cost/time tradeoffInternational Journal of Project Management, 1995
- Fast simulation of rare events in queueing and reliability modelsACM Transactions on Modeling and Computer Simulation, 1995
- Project compression: A method for speeding up resource constrained projects which preserve the activity scheduleEuropean Journal of Operational Research, 1990
- Simulation and the Monte Carlo MethodWiley Series in Probability and Statistics, 1981
- A Dynamic Programming Algorithm for Decision CPM NetworksOperations Research, 1979