×

Project scheduling under uncertainty: survey and research potentials. (English) Zbl 1066.90050

Summary: The vast majority of the research efforts in project scheduling assume complete information about the scheduling problem to be solved and a static deterministic environment within which the pre-computed baseline schedule will be executed. However, in the real world, project activities are subject to considerable uncertainty, which is gradually resolved during project execution. In this survey we review the fundamental approaches for scheduling under uncertainty: reactive scheduling, stochastic project scheduling, fuzzy project scheduling, robust (proactive) scheduling and sensitivity analysis. We discuss the potentials of these approaches for scheduling under uncertainty projects with deterministic network evolution structure.

MSC:

90B50 Management decision making, including multiple objectives
90B35 Deterministic scheduling theory in operations research

Software:

FULPAL; PSPLIB; RanGen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051
[2] Akturk, M. S.; Gorgulu, E., Match-up scheduling under a machine breakdown, European Journal of Operational Research, 112, 81-97 (1999) · Zbl 0937.90029
[3] Alagöz, O.; Azizoglu, M., Rescheduling of identical parallel machines under machine eligibility constraints, European Journal of Operational Research, 149, 523-532 (2003) · Zbl 1033.90031
[4] Aloulou, M.A., Portmann, M.-C., Vignier, A., 2002. Predictive-reactive scheduling for the single machine problem. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April; Aloulou, M.A., Portmann, M.-C., Vignier, A., 2002. Predictive-reactive scheduling for the single machine problem. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April
[5] Artigues, C.; Roubellat, F., A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes, European Journal of Operational Research, 127, 297-316 (2000) · Zbl 0990.90034
[6] Artigues, C.; Roubellat, F.; Billaut, J.-C., Characterization of a set of schedules in a resource-constrained multi-project scheduling problem with multiple modes, International Journal of Industrial Engineering-Theory, Applications and Practice, 6, 2, 112-122 (1999)
[7] Aytug, H., Lawley, M.A., McKay, K., Mohan, S., Uzsoy, R., in press. Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research; Aytug, H., Lawley, M.A., McKay, K., Mohan, S., Uzsoy, R., in press. Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research · Zbl 1115.90025
[8] Bean, J. C.; Birge, J. R.; Mittenthal, J.; Noon, C. E., Match-up scheduling with multiple resources, release dates and disruptions, Operations Research, 39, 3, 470-483 (1991) · Zbl 0742.90041
[9] Billaut, J. C.; Roubellat, F., A new method for workshop real time scheduling, International Journal of Production Research, 34, 6, 1555-1579 (1996) · Zbl 0927.90027
[10] Billaut, J. C.; Roubellat, F., Characterization of a set of schedules in a multiple resource context, Journal of Decision Systems, 5, 1-2, 95-109 (1996)
[11] Bowers, J. A., Criticality in resource constrained networks, Journal of the Operational Research Society, 46, 80-91 (1995) · Zbl 0829.90071
[12] Briand, C., Despontin, E., Roubellat, F., 2002. Scheduling with time lags and preferences: A heuristic. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April; Briand, C., Despontin, E., Roubellat, F., 2002. Scheduling with time lags and preferences: A heuristic. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April
[13] Bruno, J.; Coffman, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, 17, 7, 382-387 (1974) · Zbl 0283.68039
[14] Calhoun, K. M.; Deckro, R. F.; Moore, J. T.; Chrissis, J. W.; Van Hove, J. C., Planning and re-planning in project and production planning, Omega, 30, 155-170 (2002)
[15] Czyzak, P.; Jaskievicz, A., Metaheuristic technique for solving multiobjective investment planning problem, Control and Cybernetics, 25, 177-187 (1996)
[16] Daniels, R. L.; Carrillo, J. E., β-robust scheduling for single-machine systems with uncertain processing times, IIE Transactions, 29, 977-985 (1997)
[17] Daniels, R. L.; Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41, 2, 363-376 (1995) · Zbl 0832.90050
[18] Davenport, A.J., Beck, J.C., 2002. A survey of techniques for scheduling with uncertainty, Unpublished manuscript. Available from <http://www.eil.utoronto.ca/profiles/chris/gz/uncertainty-survey.ps; Davenport, A.J., Beck, J.C., 2002. A survey of techniques for scheduling with uncertainty, Unpublished manuscript. Available from <http://www.eil.utoronto.ca/profiles/chris/gz/uncertainty-survey.ps
[19] Davenport, A.J., Gefflot, C., Beck, J.C., 2001. Slack-based techniques for robust schedules. Paper presented at the Constraints and Uncertainty Workshop, Seventh International Conference on Principles and Practice of Constraint Programming, November 26-December 1, Paphos, Cyprus; Davenport, A.J., Gefflot, C., Beck, J.C., 2001. Slack-based techniques for robust schedules. Paper presented at the Constraints and Uncertainty Workshop, Seventh International Conference on Principles and Practice of Constraint Programming, November 26-December 1, Paphos, Cyprus
[20] Demeulemeester, E.; Vanhoucke, M.; Herroelen, W., RanGen: A random generator for activity-on-the-node networks, Journal of Scheduling, 6, 17-38 (2003) · Zbl 1154.90440
[21] Demeulemeester, E. L.; Herroelen, W. S., Project Scheduling-A Research Handbook (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1059.90068
[22] Dorn, J.; Kerr, R.; Thalhammer, G., Reactive scheduling: improving robustness of schedules and restricting the effects of shop floor disturbances by fuzzy reasoning, International Journal of Human-Computer Studies, 42, 687-704 (1995) · Zbl 0831.90072
[23] Elmaghraby, S.E.E., 2000. Optimal Resource Allocation and Budget Estimation in Multimodal Activity Networks, Research Paper. North Carolina State University at Raleigh, North Carolina, USA; Elmaghraby, S.E.E., 2000. Optimal Resource Allocation and Budget Estimation in Multimodal Activity Networks, Research Paper. North Carolina State University at Raleigh, North Carolina, USA
[24] El Sakkout, H.; Wallace, M., Probe backtrack search for minimal perturbation in dynamic scheduling, Constraints, 5, 4, 359-388 (2000) · Zbl 0970.68014
[25] Fernandez, A.A., 1995. The optimal solution to the resource-constrained project scheduling problem with stochastic task durations. Unpublished Doctoral Dissertation. University of Central Florida; Fernandez, A.A., 1995. The optimal solution to the resource-constrained project scheduling problem with stochastic task durations. Unpublished Doctoral Dissertation. University of Central Florida
[26] Fernandez, A. A.; Armacost, R. L.; Pet-Edwards, J., The role of the non-anticipativity constraint in commercial software for stochastic project scheduling, Computers and Industrial Engineering, 31, 233-236 (1996)
[27] Fernandez, A. A.; Armacost, R. L.; Pet-Edwards, J., Understanding simulation solutions to resource-constrained project scheduling problems with stochastic task durations, Engineering Management Journal, 10, 5-13 (1998)
[28] Gao, H., 1995. Building robust schedules using temporal protection-an empirical study of constraint based scheduling under machine failure uncertainty. Master’s Thesis. Department of Industrial Engineering, University of Toronto; Gao, H., 1995. Building robust schedules using temporal protection-an empirical study of constraint based scheduling under machine failure uncertainty. Master’s Thesis. Department of Industrial Engineering, University of Toronto
[29] Ghosh, S., 1996. Guaranteeing fault tolerance through scheduling in real-time systems. Ph.D. thesis. University of Pittsburgh; Ghosh, S., 1996. Guaranteeing fault tolerance through scheduling in real-time systems. Ph.D. thesis. University of Pittsburgh
[30] Ghosh, S., Melhem, R., Mossé, D., 1995. Enhancing Real-Time Schedules to Tolerate Transient Faults, Real-Time Systems Symposium; Ghosh, S., Melhem, R., Mossé, D., 1995. Enhancing Real-Time Schedules to Tolerate Transient Faults, Real-Time Systems Symposium
[31] Gillies, D. W.; Liu, J. W.S., Scheduling tasks with and/or precedence constraints, SIAM Journal on Computing, 24, 797-810 (1995) · Zbl 0830.68012
[32] Goldratt, E., Critical Chain (1997), The North River Press
[33] Golenko-Ginzburg, D.; Gonik, A., Stochastic network project scheduling with non-consumable limited resources, International Journal of Production Economics, 48, 29-37 (1997)
[34] Golenko-Ginzburg, D.; Gonik, A., A heuristic for network project scheduling with random activity durations depending on the resource allocation, International Journal on Production Economics, 55, 149-162 (1998)
[35] Gutjahr, W. J.; Strauss, C.; Wagner, E., A stochastic branch-and-bound approach to activity crashing in project management, INFORMS Journal on Computing, 12, 2, 125-135 (2000) · Zbl 1034.90005
[36] Hall, N., Posner, M., 2000a. Sensitivity analysis for intractable scheduling problems, Research paper. The Ohio State University; Hall, N., Posner, M., 2000a. Sensitivity analysis for intractable scheduling problems, Research paper. The Ohio State University
[37] Hall, N., Posner, M., 2000b. Sensitivity analysis for efficiently solvable scheduling problems, Research paper. The Ohio State University; Hall, N., Posner, M., 2000b. Sensitivity analysis for efficiently solvable scheduling problems, Research paper. The Ohio State University
[38] Hapke, M.; Jaskievicz, A.; Slowinski, R., Fuzzy project scheduling system for software development, Fuzzy Sets and Systems, 21, 101-117 (1994)
[39] Hapke, M.; Jaskievicz, A.; Slowinski, R., Fuzzy multi-mode resource-constrained project scheduling with multiple objectives, (Weglarz, J., Project Scheduling-Recent Models, Algorithms and Applications (1999), Kluwer Academic Publishers), 355-382, (Chapter 16)
[40] Hapke, M.; Slowinski, R., Fuzzy priority heuristics for project scheduling, Fuzzy Sets and Systems, 83, 291-299 (1996)
[41] Hapke, M.; Slowinski, R., Fuzzy set approach to multi-objective and multi-mode project scheduling under uncertainty, (Slowinski, R.; Hapke, M., Scheduling Under Fuzziness (2000), Physica-Verlag: Physica-Verlag Heidelberg), 197-221, (Chapter 9) · Zbl 0965.90024
[42] Herroelen, W.; Leus, R., The construction of stable project baseline schedules, European Journal of Operational Research, 156, 550-565 (2004) · Zbl 1056.90066
[43] Igelmund, G.; Radermacher, F. J., Preselective strategies for the optimization of stochastic project networks under resource constraints, Networks, 13, 1-28 (1983) · Zbl 0504.90039
[44] Igelmund, G.; Radermacher, F. J., Algorithmic approaches to preselective strategies for stochastic scheduling problems, Networks, 13, 29-48 (1983) · Zbl 0504.90040
[45] Jensen, M.T., 2001. Robust and flexible scheduling with evolutionary computation. Ph.D. thesis. Department of Computer Science, University of Aarhus, Denmark; Jensen, M.T., 2001. Robust and flexible scheduling with evolutionary computation. Ph.D. thesis. Department of Computer Science, University of Aarhus, Denmark
[46] Jørgenson, T., 1999. Project scheduling-a stochastic dynamic decision problem. Doctoral Dissertation. Norwegian University of Science and Technology, Trondheim, Norway; Jørgenson, T., 1999. Project scheduling-a stochastic dynamic decision problem. Doctoral Dissertation. Norwegian University of Science and Technology, Trondheim, Norway
[47] Kolisch, R.; Sprecher, A., PSPLIB-A project scheduling library, European Journal of Operational Research, 96, 205-216 (1996) · Zbl 0947.90587
[48] Kouvelis, P.; Daniels, R. L.; Vairaktarakis, G., Robust scheduling of a two-machine flow shop with uncertain processing times, IIE Transactions, 32, 421-432 (2000)
[49] Kouvelis, P.; Yu, G., Robust Discrete Optimization and its Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0873.90071
[50] Laguna, M.; Lino, P.; Pérez, A.; Quintanilla, S.; Valls, V., Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines, European Journal of Operational Research, 127, 444-457 (2000) · Zbl 0990.90031
[51] Laslo, Z., Activity time-cost tradeoffs under time and cost chance constraints, Computers and Industrial Engineering, 44, 365-384 (2003)
[52] Leon, V. J.; Wu, S. D.; Storer, R. H., Robustness measures and robust scheduling for job shops, IIE Transactions, 26, 5, 32-43 (1994)
[53] Leus, R., 2003. The generation of stable project plans-complexity and exact algorithms, Ph.D. Thesis, K.U. Leuven; Leus, R., 2003. The generation of stable project plans-complexity and exact algorithms, Ph.D. Thesis, K.U. Leuven
[54] Leus, R.; Herroelen, W., Stability and resource allocation in project planning, IIE Transactions, 36, 667-682 (2004)
[55] Mauguière, P., Billaut, J.-C., Artigues, C., 2002. Grouping jobs on a single machine with heads and tails to represent a family of dominant schedules. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April; Mauguière, P., Billaut, J.-C., Artigues, C., 2002. Grouping jobs on a single machine with heads and tails to represent a family of dominant schedules. Paper presented at the 8th Workshop on Project Management and Scheduling, Valencia, 3-5 April
[56] Mehta, S. V.; Uzsoy, R. M., Predictable scheduling of a job shop subject to breakdowns, IEEE Transactions on Robotics and Automation, 14, 3, 365-378 (1998)
[57] Mehta, S. V.; Uzsoy, R., Predictive scheduling of a single machine subject to breakdowns, International Journal of Computer Integrated Manufacturing, 12, 1, 15-38 (1999)
[58] Möhring, R. H.; Radermacher, F. J.; Weiss, G., Stochastic scheduling problems. I. General strategies, ZOR-Zeitschrift für Operations Research, 28, 193-260 (1984) · Zbl 0553.90058
[59] Möhring, R. H.; Radermacher, F. J.; Weiss, G., Stochastic scheduling problems. II. Set strategies, ZOR-Zeitschrift für Operations Research, 29, 65-104 (1985) · Zbl 0568.90043
[60] Möhring, R.H., Skutella, M., Stork, F., 2000. Scheduling with AND/OR Precedence Constraints, Technical Report 689/2000. Department of Mathematics, Technische Universität Berlin, Germany; Möhring, R.H., Skutella, M., Stork, F., 2000. Scheduling with AND/OR Precedence Constraints, Technical Report 689/2000. Department of Mathematics, Technische Universität Berlin, Germany
[61] Möhring, R. H.; Stork, F., Linear preselective policies for stochastic project scheduling, Mathematical Methods of Operations Research, 52, 501-515 (2000) · Zbl 1023.90033
[62] Naegler, G.; Schoenherr, S. S., Resource allocation in a network model-the Leinet system, (Slowinski, R.; Weglarz, J., Advances in Project Scheduling (1989), Elsevier)
[63] Neumann, K., Scheduling of projects with stochastic evolution structure, (Weglarz, J., Project Scheduling-Recent Models, Algorithms and Applications (1999), Kluwer Academic publishers: Kluwer Academic publishers Boston), 309-332, (Chapter 14)
[64] Özdamar, L.; Alanya, E., Uncertainty modelling in software development projects (with case study), Annals of Operations Research, 102, 157-178 (2000) · Zbl 0991.90522
[65] Patterson, J. H., A comparison of exact procedures for solving the multiple constrained resource project scheduling problem, Management Science, 30, 854-867 (1984)
[66] Penz, B.; Rapine, C.; Trystram, D., Sensitivity analysis of scheduling algorithms, European Journal of Operational Research, 134, 606-615 (2001) · Zbl 0984.90044
[67] Pet-Edwards, J., 1996. A simulation and genetic algorithm approach to stochastic resource-constrained project scheduling. Southcon Conference Record 1996. IEEE, Pascataway, NJ, pp. 333-338; Pet-Edwards, J., 1996. A simulation and genetic algorithm approach to stochastic resource-constrained project scheduling. Southcon Conference Record 1996. IEEE, Pascataway, NJ, pp. 333-338
[68] Pet-Edwards, J., Selim, B., Armacost, R.L., Fernandez, A., 1998. Minimizing risk in stochastic resource-constrained project scheduling. Paper presented at the INFORMS Fall Meeting, Seattle, October 25-28; Pet-Edwards, J., Selim, B., Armacost, R.L., Fernandez, A., 1998. Minimizing risk in stochastic resource-constrained project scheduling. Paper presented at the INFORMS Fall Meeting, Seattle, October 25-28
[69] Radermacher, F. J., Scheduling of project networks, Annals of Operations Research, 4, 227-252 (1985) · Zbl 0693.90046
[70] Rommelfanger, H., FULPAL: An Interactive Method for Solving (Multiobjective) Fuzzy Linear Programming Problems, (Slowinski, R.; Teghem, J., Stochastic Versus Fuzzy Approaches to Multiobjective Mathematical Programming Under Uncertainty (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 279-299, (Section 5) · Zbl 0734.90120
[71] Sabuncuoglu, I.; Bayiz, M., Analysis of reactive scheduling problems in a job shop environment, European Journal of Operational Research, 126, 567-586 (2000) · Zbl 0976.90045
[72] Sadeh, N., Otsuka, S., Schelback, R., 1993. Predictive and reactive scheduling with the microboss production scheduling and control system. In: Proceedings of the IJCAI-93 Workshop on Knowledge-Based Production Planning, Scheduling and Control, pp. 293-306; Sadeh, N., Otsuka, S., Schelback, R., 1993. Predictive and reactive scheduling with the microboss production scheduling and control system. In: Proceedings of the IJCAI-93 Workshop on Knowledge-Based Production Planning, Scheduling and Control, pp. 293-306
[73] Scholl, A., Robuste Planung und Optimierung-Grundlagen, Konzepte und Methoden, Experimentelle Untersuchungen (2001), Physica-Verlag: Physica-Verlag Heidelberg
[74] Sevaux, M., Sörensen, K., 2002a. A genetic algorithm for robust schedules. Paper presented at the 8th International Workshop on Project Management and Scheduling, Valencia, April 3-5; Sevaux, M., Sörensen, K., 2002a. A genetic algorithm for robust schedules. Paper presented at the 8th International Workshop on Project Management and Scheduling, Valencia, April 3-5
[75] Sevaux, M., Sörensen, K., 2002b. A genetic algorithm for robust schedules in a just-in-time environment, Research Report LAMIH/SP-2003-1. University of Valenciennes, France; Sevaux, M., Sörensen, K., 2002b. A genetic algorithm for robust schedules in a just-in-time environment, Research Report LAMIH/SP-2003-1. University of Valenciennes, France
[76] (Slowinski, R.; Hapke, M., Scheduling under Fuzziness (2000), Physica-Verlag: Physica-Verlag Heidelberg)
[77] Smith, S. S., Reactive scheduling systems, (Brown, D. E.; Scherer, W. T., Intelligent Scheduling Systems (1994), Kluwer)
[78] Stork, F., 2000. Branch-and-bound algorithms for stochastic resource-constrained project scheduling, Research Report No. 702/2000. Technische Universität Berlin; Stork, F., 2000. Branch-and-bound algorithms for stochastic resource-constrained project scheduling, Research Report No. 702/2000. Technische Universität Berlin
[79] Stork, F., 2001. Stochastic resource-constrained project scheduling. Ph.D. Thesis. Technische Universität Berlin; Stork, F., 2001. Stochastic resource-constrained project scheduling. Ph.D. Thesis. Technische Universität Berlin
[80] Szelke, E.; Kerr, R. M., Knowledge-based reactive scheduling, Production Planning and Control, 5, 2, 124-145 (1994)
[81] Tavares, L. V.; Ferreira, J. A.A.; Coelho, J. S., On the optimal management of project risk, European Journal of Operational Research, 107, 451-469 (1998) · Zbl 0943.90043
[82] Tereso, A.P., 2002. Project management-adaptive resource allocation in multimodal activity networks. PhD Thesis. Universidade do Minho, Portugal; Tereso, A.P., 2002. Project management-adaptive resource allocation in multimodal activity networks. PhD Thesis. Universidade do Minho, Portugal
[83] Tereso, A.P., Araújo, M.M.T., Elmaghraby, S.E., 2003. Experimental results of an adaptive resource allocation technique to stochastic multimodal projects. In: Proceedings of the International Conference on Industrial Engineering and Production Management, Porto, June 26-28; Tereso, A.P., Araújo, M.M.T., Elmaghraby, S.E., 2003. Experimental results of an adaptive resource allocation technique to stochastic multimodal projects. In: Proceedings of the International Conference on Industrial Engineering and Production Management, Porto, June 26-28
[84] Tsai, Y.W., Gemmil, D.D., 1996. Using a simulated annealing algorithm to schedule activities of resource-constrained projects, Working Paper No. 96-124. Iowa State University; Tsai, Y.W., Gemmil, D.D., 1996. Using a simulated annealing algorithm to schedule activities of resource-constrained projects, Working Paper No. 96-124. Iowa State University
[85] Tsai, Y. W.; Gemmil, D. D., Using tabu search to schedule activities of stochastic resource-constrained projects, European Journal of Operational Research, 111, 129-141 (1998) · Zbl 0948.90072
[86] Valls, V.; Laguna, M.; Lino, P.; Pérez, A.; Quintanilla, S., Project scheduling with stochastic activity interruptions, (Weglarz, J., Project Scheduling-Recent Models, Algorithms and Applications (1999), Kluwer Academic Publishers), 333-353, (Chapter 15)
[87] Vieira, G. E.; Herrmann, J. W.; Lin, E., Rescheduling manufacturing systems: A framework of strategies, policies and methods, Journal of Scheduling, 6, 39-62 (2003) · Zbl 1154.90500
[88] Wang, J. R., A fuzzy set approach to activity scheduling for product development, Journal of the Operational Research Society, 50, 1217-1228 (1999) · Zbl 1054.90552
[89] Wang, J., A fuzzy project scheduling approach to minimize schedule risk for product development, Fuzzy Sets and Systems, 127, 2, 99-116 (2002) · Zbl 0993.90053
[90] Wang, J., A fuzzy robust scheduling approach for product development projects, European Journal of Operational Research, 152, 180-194 (2004) · Zbl 1044.90038
[91] Wollmer, R. D., Critical path planning under uncertainty, Mathematical Programming Study, 25, 164-171 (1985) · Zbl 0583.90101
[92] Wu, S. D.; Storer, R. H.; Chang, P. C., One machine rescheduling heuristics with efficiency and stability as criteria, Computers and Operations Research, 20, 1-14 (1993) · Zbl 0759.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.