[en] The purpose of this paper is to propose models for
project scheduling when there is considerable uncertainty in the
activity durations, to the extent that the decision maker cannot
with confidence associate probabilities with the possible scenarios.
Our modeling techniques stem from robust optimization, which
is a theoretical framework that enables the decision maker to
produce solutions that will have a reasonably good objective value
under any likely input data scenario. We develop and implement
a scenario-relaxation algorithm and a scenario-relaxationbased
heuristic. The first algorithm produces optimal solutions
but requires excessive running times even for medium-sized
instances; the second algorithm produces high-quality solutions
for medium-sized instances and outperforms two benchmark
heuristics.
Disciplines :
Production, distribution & supply chain management
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Adlakha VG, Kulkarni VG (1989) A classified bibliography of research on stochastic PERT networks: 1966-1987. INFOR 27:272-296
Aissi H, Bazgan C, Vanderpooten D (2009) Min-max and min-max regret versions of combinatorial optimization problems: a survey. Eur J Oper Res 197:427-438
Artigues C, Michelon P, Reusser S (2003) Insertion techniques for static and dynamic resource-constrained project scheduling. Eur J Oper Res 149:249-267
Artigues C, Roubellat F (2000) A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple modes. Eur J Oper Res 127:297-316
Ashtiani B, Leus R, Aryanezhad MB (2011) New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing. J Sched 14(2):157-171
Assavapokee T, Realff MJ, Ammons JC (2008a) A new min-max regret robust optimization approach for interval data uncertainty. J Optim Theory Appl 137:297-316
Assavapokee T, Realff MJ, Ammons JC, Hong IH (2008b) Scenario relaxation algorithm for finite scenario-based min-max regret and min-max relative regret robust optimization. Comput Oper Res 35:2093-2102
Averbakh I (2000) Minmax regret solutions for minimax optimization problems with uncertainty. Oper Res Lett 27:57-65
Averbakh I (2005) Computing and minimizing the relative regret in combinatorial optimization with interval data. Discrete Optim 2:273-287
Averbakh I, Lebedev V (2004) Interval data minmax regret network optimization problems. Discrete Appl Math 138:289-301
Balas E (1971) Project scheduling with resource constraints. In: Beale EML (eds) Applications of Mathematical Programming Techniques, The English Universities Press Ltd, London, pp 187-200
Ballestín F, Leus R (2009) Resource-constrained project scheduling for timely project completion with stochastic activity durations. Prod Oper Manag 18(4):459-474
Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper Res Lett 25:1-13
Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program 88:411-424
Ben-Tal A, Nemirovski A (2002) Robust optimization - methodology and applications. Math Program 92:453-480
Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98:49-71
Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52:35-53
Blazewicz J, Lenstra JK, Rinnooy Kan AHG (1983) Scheduling subject to resource constraints: Classification and complexity. Discrete Appl Math 5:11-24
Bowers JA (1995) Criticality in resource constrained networks. J Oper Res Soc 46:80-91
Daniels RL, Kouvelis P (1995) Robust scheduling to hedge against processing time uncertainty in single-stage production. Manag Sci 41:363-376
Demassey S (2008) Mathematical programming formulations and lower bounds. In: Artigues C, Demassey S, Néron E (eds) Resource-constrained project scheduling. Models, algorithms, extensions and applications, ISTE Ltd. and John Wiley and Sons Inc, London, pp 49-62
Demeulemeester E, Herroelen W (1992) A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Manag Sci 38:1803-1818
Demeulemeester E, Herroelen W (2002) Project scheduling. Kluwer, Dordrecht
Demeulemeester E, Vanhoucke M, Herroelen W (2003) A random network generator for activity-on-the-node networks. J Sched 6:13-34
Elmaghraby SE (1977) Activity networks: project planning and control by network models. Wiley, New York
French S (1988) Decision theory. An introduction to the mathematics of rationality. Ellis Horwood Limited, Chichester
Glover F, Laguna M (1997) Tabu search. Kluwer, Boston
Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653-684
Hughes MW (1986) Why projects fail: the effects of ignoring the obvious. Ind Eng 18:14-18
Hurwicz L (1951) Optimality criteria for decision making under ignorance. Cowles Commission Discussion Paper no. 370
Igelmund G, Radermacher FJ (1983) Preselective strategies for the optimization of stochastic project networks under resource constraints. Networks 13:1-28
Jørgensen T (1999) Project scheduling as a stochastic dynamic decision problem. PhD thesis, Norwegian University of Science and Technology, Trondheim, Norway
Kasperski A (2008) Discrete optimization with interval data. Minmax regret and fuzzy approach, volume 228 of studies in fuzziness and soft computing. Springer, Berlin, Heidelberg
Knight FH (1921) Risk, uncertainty, and profit. Houghton Mifflin, Boston
Kolisch R (1996) Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur J Oper Res 90:320-333
Kolisch R, Padman R (2001) An integrated survey of deterministic project scheduling. Omega 29:249-272
Kouvelis P, Daniels RL, Vairaktarakis G (2000) Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans 32:421-432
Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer, Dordrecht
Kulkarni VG, Adlakha VG (1986) Markov and Markov-regenerative PERT networks. Oper Res 34:769-781
Lebedev V, Averbakh I (2006) Complexity of minimizing the total flow time with interval data and minmax regret criterion. Discrete Appl Math 154:2167-2177
Leus R (2011a) Resource allocation by means of project networks: complexity results. Networks 58(1):59-67
Leus R (2011b) Resource allocation by means of project networks: dominance results. Networks 58(1):50-58
Leus R, Herroelen W (2004) Stability and resource allocation in project planning. IIE Trans 36:667-682
Loch CH, De Meyer A, Pich MT (2006) A new approach to managing high uncertainty and risk in projects. Wiley, New York
Ludwig A, Möhring RH, Stork F (2001) A computational study on bounding the makespan distribution in stochastic project networks. Ann Oper Res 102:49-64
Malcolm DG, Rosenbloom JM, Clark CE, Fazar W (1959) Application of a technique for research and development program evaluation. Oper Res 7:646-669
Montemanni R (2007) A mixed integer programming formulation for a single machine robust scheduling with interval data. J Math Model Algorithms 6:287-296
Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper Res 43:264-281
Naegler G, Schoenherr S (1989) Resource allocation in a network model - the Leinet system. In: Slowinski R, Weglarz J (eds) Advances in project scheduling, chapter II8, Elsevier, Amsterdam
Neumann K, Schwindt C, Zimmermann J (2003) Project scheduling with time windows and scarce resources: temporal and resource-constrained project scheduling with regular and nonregular objective functions. Springer, Berlin
Nikulin Y (2006) Robustness in combinatorial optimization and scheduling theory: an extended annotated bibliography. Technical Report 606, Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel, Kiel, Germany
Rosenhead J, Elton M, Gupta SK (1972) Robustness and optimality as criteria for strategic decisions. Oper Res Q 23:413-431
Roy B, Sussmann B (1964) Les problèmes d'ordonnancement avec contraintes disjonctives. Technical Report Note DS no. 9 bis, SEMA, Paris, France
Savage LJ (1951) The theory of statistical decision. J Am Stat Assoc 46:55-67
Stork F (2001) Stochastic resource-constrained project scheduling. PhD thesis, TU Berlin, Berlin, Germany
Stork F, Uetz M (2005) On the generation of circuits and minimal forbidden sets. Math Program 102:185-203
Wald A (1950) Statistical decision functions. Wiley, London
Walley P (1991) Statistical reasoning with imprecise probabilities, volume 42 of monographs on statistics and applied probability. Chapman and Hall, London
Wiest JD, Levy FK (1969) A management guide to PERT/CPM with GERT/PDM/DCPM and other networks. Prentice-Hall, Englewood Cliffs, NJ
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
