Expectation and Chance-Constrained Models and Algorithms for Insuring Critical Paths
In this paper, we consider a class of two-stage stochastic optimization problems arising in the protection of vital arcs in a critical path network. A project is completed after a series of dependent tasks are all finished. We analyze a problem in which task finishing times are uncertain but can be insured a priori to mitigate potential delays. A decision maker must trade off costs incurred in insuring arcs with expected penalties associated with late project completion times, where lateness penalties are assumed to be lower semicontinuous nondecreasing functions of completion time. We provide decomposition strategies to solve this problem with respect to either convex or nonconvex penalty functions. In particular, for the nonconvex penalty case, we employ the reformulation-linearization technique to make the problem amenable to solution via Benders decomposition. We also consider a chance-constrained version of this problem, in which the probability of completing a project on time is sufficiently large. We demonstrate the computational efficacy of our approach by testing a set of size-and-complexity diversified problems, using the sample average approximation method to guide our scenario generation.
Volume (Year): 56 (2010)
Issue (Month): 10 (October)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
- Thomas J. Hindelang & John F. Muth, 1979. "A Dynamic Programming Algorithm for Decision CPM Networks," Operations Research, INFORMS, vol. 27(2), pages 225-241, April.
- Elmaghraby, S. E. & Ferreira, A. A. & Tavares, L. V., 2000. "Optimal start times under stochastic activity durations," International Journal of Production Economics, Elsevier, vol. 64(1-3), pages 153-164, March.
- Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
- Golenko-Ginzburg, Dimitri & Gonik, Aharon, 1998. "A heuristic for network project scheduling with random activity durations depending on the resource allocation," International Journal of Production Economics, Elsevier, vol. 55(2), pages 149-162, July.
- R. A. Bowman, 1995. "Efficient Estimation of Arc Criticalities in Stochastic Activity Networks," Management Science, INFORMS, vol. 41(1), pages 58-67, January.
- John M. Burt, Jr. & Mark B. Garman, 1971. "Conditional Monte Carlo: A Simulation Technique for Stochastic Network Analysis," Management Science, INFORMS, vol. 18(3), pages 207-217, November.
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:56:y:2010:i:10:p:1794-1814. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.