We investigate resource‐constrained project scheduling with stochastic activity durations. Various objective functions related to timely project completion are examined, as well as the correlation between these objectives. We develop a GRASP‐heuristic to produce high‐quality solutions, using so‐called descriptive sampling. The algorithm outperforms existing algorithms for expected‐makespan minimization. The distribution of the possible makespan realizations for a given scheduling policy is also studied.
AdlakhaV. G.KulkarniV. G.. 1989. A classified bibliography of research on stochastic PERT networks: 1966–1987. INFOR 27(3): 272–296.
2.
AiexR. M.ResendeM. G. C.RibeiroC. C.. 2002. Probability distribution of solution time in GRASP: An experimental investigation. J. Heuristics 8(3): 343–373.
AvramidisA. N.BauerK. W.Jr.WilsonJ. R.. 1991. Simulation of stochastic activity networks using path control variates. Naval Res. Log.38(2): 183–201.
5.
BallestínF.2007. When it is worthwile to work with the stochastic RCPSP?J. Scheduling10(3): 153–166.
6.
BayizM.CorbettC. J.. 2005. Coordination and incentive contracts in project management under asymmetric information. Working Paper CC31, Anderson Graduate School of Management, University of California, Los Angeles.
7.
BlazewiczJ.LenstraJ.Rinnooy‐KanA.. 1983. Scheduling subject to resource constraints – classification and complexity. Discrete Appl. Math.5(1): 11–24.
8.
ChoJ. G.YumB. J.. 1997. An uncertainty importance measure of activities in PERT networks. Int. J. Prod. Res.35(10): 2737–2757.
9.
D'AgostinoR. B.1986. Tests for the normal distribution. D'AgostinoR. B.StephensM. A. eds. Goodness‐of‐Fit Techniques. Marcel Dekker, New York, 367–419.
10.
DebelsD.DeReyckB.LeusR.VanhouckeM.. 2006. A hybrid scatter search/electromagnetism meta‐heuristic for project scheduling. Eur. J. Oper. Res.169(2): 638–653.
11.
DemeulemeesterE.HerroelenW.. 2002. Project Scheduling – A Research Handbook. Kluwer Academic Publishers, Boston.
12.
DemeulemeesterE.VanhouckeM.HerroelenW.. 2003. A random network generator for activity‐on‐the‐node networks. J. Schedul.6(1): 13–34.
13.
DodinB.1996. Determining the optimal sequences and the distributional properties of their completion times in stochastic flow shops. Comput. Oper. Res.23(9): 829–843.
14.
ElmaghrabyS. E.FathiY.TanerM. R.. 1999. On the sensitivity of project variability to activity mean duration. Int. J. Prod. Econ.62(3): 219–232.
15.
FeoT. A.ResendeM. G. C.. 1995. Greedy randomized adaptive search procedures. J. Global Optim.6(2): 109–133.
16.
FeoT. A.ResendeM. G. C.SmithS.. 1994. A greedy randomized adaptive search procedure for maximum independent set. Oper. Res.42(5): 860–878.
17.
FrenchS.1988. Decision Theory. An Introduction to the Mathematics of Rationality. Ellis Horwood Limited, Chichester, UK.
18.
GerchakY.2000. On the allocation of uncertainty‐reduction effort to minimize total variability. IIE Trans.32(5): 403–407.
19.
Golenko‐GinzburgD.GonikA.. 1997. Stochastic network project scheduling with non‐consumable limited resources. Int. J. Prod. Econ.48(1): 29–37.
20.
GrahamR. L.1966. Bounds on multiprocessing timing anomalies. Bell Syst. Techn. J.45: 1563–1581.
21.
GrantF. H.III1983. A note on “efficiency of the antithetic variate method for simulating stochastic networks”. Manag. Sci.29(3): 381–384.
22.
GutierrezG. J.PaulA.. 2001. Robustness to variability in project networks. IIE Trans.33(8): 649–660.
23.
GutjahrW. J.StraussC.WagnerE.. 2000. A stochastic branch‐and‐bound approach to activity crashing in project management. INFORMS J. Comput.12(2): 125–135.
24.
HagstromJ. N.1988. Computational complexity of PERT problems. Networks18(2): 139–147.
25.
HartJ. P.ShoganA. W.. 1987. Semi‐greedy heuristics: An empirical study. Oper. Res. Lett. 6(3): 107–114.
26.
HartmannS.1998. A competitive genetic algorithm for resource‐constrained project scheduling. Naval Res. Log.45(7): 733–750.
27.
HartmannS.KolischR.. 2000. Experimental evaluation of state‐of‐the‐art heuristics for the resource‐constrained project scheduling problem. Eur. J. Oper. Res.127(2): 394–407.
28.
HerroelenW.2005. Project scheduling – theory and practice. Prod. Oper. Manag.14(4): 413–432.
29.
IgelmundG.RadermacherF. J.. 1983. Preselective strategies for the optimization of stochastic project networks under resource constraints. Networks13(1): 1–28.
30.
JorionP.2000. Value at Risk: The Benchmark for Controlling Market Risk. McGraw‐Hill, New York.
31.
KerznerH.1998. Project Management. Wiley, New York.
32.
KleywegtA. J.ShapiroA.Homem‐De‐MelloT.. 2001. The sample average approximation method for stochastic discrete optimization. SIAM J. Optim.12(2): 479–502.
33.
KolischR.HartmannS.. 1999. Heuristic algorithms for solving the resource‐constrained project scheduling problem: Classification and computational analysis. WeglarzJ. ed. Project Scheduling – Recent Models, Algorithms and Applications. Kluwer Academic Publishers, Boston, 147–178.
34.
KolischR.PadmanR.. 2001. An integrated survey of deterministic project scheduling. Omega29(3): 249–272.
35.
KolischR.SprecherA.. 1996. PSPLIB – a project scheduling problem library. Eur. J. Oper. Res.96(1): 205–216.
36.
KouvelisP.YuG.. 1997. Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht.
37.
LeusR.HerroelenW.. 2004. Stability and resource allocation in project planning. IIE Trans.36(7): 667–682.
38.
LinnetK.1988. Testing normality of transformed data. Appl. Stat.37(2): 180–186.
39.
LudwigA.MöhringR. H.StorkF.. 2001. A computational study on bounding the makespan distribution in stochastic project networks. Ann. Oper. Res.102(1–4): 49–64.
40.
MöhringR. H.RadermacherF. J.. 1989. The order‐theoretic approach to scheduling: The stochastic case. SlowinskiR.WeglarzJ. eds. Advances in Project Scheduling. Elsevier, Amsterdam, 497–531.
41.
NeumannK.SchwindtC.ZimmermannJ.. 2002. Project Scheduling with Time Windows and Scarce Resources. Springer, Berlin.
42.
NewboldR. C.1998. Project Management in the Fast Lane. The St. Lucie Press/APICS Series on Constraints Management, Boca Raton, FL.
43.
PattersonJ. H.1984. A comparison of exact approaches for solving the multiple constrained resource project scheduling problem. Manag. Sci.30(7): 854–867.
44.
PortougalV.TrietschD.. 1998. Makespan‐related criteria for comparing schedules in stochastic environments. J. Oper. Res. Soc.49(11): 1188–1195.
45.
SalibyE.1990. Descriptive sampling: A better approach to Monte Carlo simulation. J. Oper. Res. Soc. 41(12): 1133–1142.
46.
SalibyE.1997. Descriptive sampling: An improvement over Latin hypercube sampling. AndradóttirS.HealyK. J.WithersD. H.NelsonB. L. eds. Proceedings of the 1997 Winter Simulation Conference. Institute of Electrical and Electronics Engineers, Piscataway, NJ. 230–233.
47.
SchuylerJ.2001. Risk and Decision Analysis in Projects. Project Management Institute, Newtown Square, PA.
48.
SilverE. A.PykeD. F.PetersonR.. 1998. Inventory Management and Production Planning and Scheduling. John Wiley & Sons, New York.
49.
SmithP. G.ReinertsenD. G.. 1991. Developing Projects in Half the Time. Van Nostrand Reinhold, New York.
50.
StorkF.2001. Stochastic resource‐constrained project scheduling. Ph.D. thesis, Technische Universität Berlin.
51.
SullivanR. S.HayyaJ. C.SchaulR.. 1982. Efficiency of the antithetic variate method for simulating stochastic networks. Manag. Sci.28(5): 563–572.
52.
TsaiY.‐W.GemmillD. D.. 1998. Using tabu search to schedule activities of stochastic resource‐constrained projects. Eur. J. Oper. Res.111(1): 129–141.
53.
VallsV.BallestínF.QuintanillaS.. 2005. Justification and RCPSP: A technique that pays. Eur. J. Oper. Res. 165(2): 375–386.
