Project scheduling under uncertainty: Survey and research potentials
Introduction
The project scheduling literature largely concentrates on the generation of a precedence and resource feasible schedule that “optimizes” the scheduling objective(s) (most often the project duration) and that should serve as a baseline schedule for executing the project. Such a baseline schedule (also called a predictive schedule or pre-schedule) serves very important functions (Aytug et al., in press; Mehta and Uzsoy, 1998). The first is to allocate resources to the different activities to optimize some measure of performance. The second, as also pointed out by Wu et al. (1993), is to serve as a basis for planning external activities such as material procurement, preventive maintenance and delivery of orders to external or internal customers. Baseline schedules serve as a basis for communication and coordination with external entities in the company's inbound and outbound supply chain. Based on the baseline schedule, commitments are made to subcontractors to deliver materials, support activities are planned (set-ups, supporting personnel), and due dates are set for the delivery of project results. Moreover, from a modelling viewpoint, many real-life scheduling problems such as course scheduling, sports time-tabling, railway and airline scheduling, can be modelled as variations of resource-constrained project scheduling problems. In these environments executing activities according to the pre-schedule is a must that is imposed by the customer: although “technically” possible, activities are not started prior to their scheduled starting time.
During project execution, however, project activities are subject to considerable uncertainty that may lead to numerous schedule disruptions. This uncertainty may stem from a number of possible sources: activities may take more or less time than originally estimated, resources may become unavailable, material may arrive behind schedule, ready times and due dates may have to be changed, new activities may have to be incorporated or activities may have to be dropped due to changes in the project scope, weather conditions may cause severe delays, etc. A disrupted schedule incurs higher costs due to missed due dates and deadlines, resource idleness, higher work-in-process inventory and increased system nervousness due to frequent rescheduling. As a result, the validity of static deterministic scheduling has been questioned and/or heavily criticised (Goldratt, 1997).
In general, we can distinguish between five approaches to dealing with uncertainty in a scheduling environment where the evolution structure of the precedence network is deterministic: reactive scheduling, stochastic scheduling, scheduling under fuzziness, proactive (robust) scheduling, and sensitivity analysis. In this paper we will discuss these approaches mainly from a project scheduling viewpoint. In those situations where the approaches were clearly conceived in a machine scheduling context, our aim is to reveal their potentials for scheduling projects under uncertainty. Stochastic project networks that have a stochastic evolution structure and feedback (GERT networks) are not the subject of this paper. A state-of-the-art survey of GERT network scheduling can be found in Neumann (1999).
The paper is organised as follows. In the next section, we survey the research efforts in the field of reactive scheduling. In Section 3 we present a classification scheme for schedule construction techniques under uncertainty. Stochastic project scheduling is discussed in Section 4. Section 5 is devoted to fuzzy project scheduling. In Section 6 we characterize robust baseline schedules and review various robustness/stability measures as well as methods for generating robust and stable schedules that may have potential application for scheduling projects under uncertainty. Sensitivity analysis is discussed in Section 7. A summary and suggestions for further research conclude the paper.
Section snippets
Reactive scheduling
Reactive scheduling does not try to cope with uncertainty in creating the baseline schedule but revises or re-optimizes the baseline schedule when an unexpected event occurs. Basically most efforts concentrate on “repairing” the baseline schedule (predictive-reactive scheduling) to take into account the unexpected events that have come up. For a review of the extensive literature in manufacturing environments we refer to Sabuncuoglu and Bayiz (2000), Szelke and Kerr (1994) and Vieira et al.
Generating a baseline schedule
The first column of Table 1 distinguishes between three basic approaches for the development of a baseline schedule. In the first approach, no baseline schedule is generated. In the second scheme, a baseline schedule is developed using a deterministic scheduling method without any anticipation of variability in the input parameters that may occur during project execution. Single point estimates are used for parameters such as activity durations. The third approach is to develop a baseline
Stochastic project scheduling
The literature on stochastic project scheduling is rather sparse (for a detailed discussion, see Chapter 9 in Demeulemeester and Herroelen, 2002). Most efforts concentrate on the so-called stochastic resource-constrained project scheduling problem which will be discussed in Section 4.1. The related special case of stochastic activity interruptions, time/cost trade-off problems and stochastic multi-mode problems are the subject of Sections 4.2 Stochastic activity interruptions, 4.3 The
Fuzzy project scheduling
The advocates of the fuzzy activity duration approach argue that probability distributions for the activity durations are unknown due to the lack of historical data. As activity durations have to be estimated by human experts, often in a non-repetitive or even unique setting, project management is often confronted with judgmental statements that are vague and imprecise. In those situations, which involve imprecision rather than uncertainty, the fuzzy set scheduling literature recommends the use
Proactive (robust) project scheduling
Numerous techniques for proactive (robust) scheduling have recently been published. The majority of publications are in the machine scheduling literature (Davenport and Beck, 2002).
Sensitivity analysis
A number of recent research efforts focus on the sensitivity analysis of machine scheduling problems (Hall and Posner, 2000a, Hall and Posner, 2000b). Sensitivity analysis addresses “What if…?” types of questions that arise from parameter changes. The authors study polynomially solvable and intractable machine scheduling problems and try to provide answers to a number of fundamental questions such as (a) what are the limits to the change of a parameter such that the solution remains optimal?
Summary and suggestions for further research
The majority of research efforts in project scheduling assume complete information about the scheduling problem to be solved and assume a static deterministic environment. Basically the research efforts aim at the generation of feasible baseline schedules that `satisfice' or optimize single or multiple objective functions. The literature on project scheduling under risk and uncertainty is rather sparse. In this paper we offer a review of the major approaches to deal with scheduling risk and
References (92)
- et al.
Match-up scheduling under a machine breakdown
European Journal of Operational Research
(1999) - et al.
Rescheduling of identical parallel machines under machine eligibility constraints
European Journal of Operational Research
(2003) - et al.
A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modes
European Journal of Operational Research
(2000) - et al.
Reactive scheduling: improving robustness of schedules and restricting the effects of shop floor disturbances by fuzzy reasoning
International Journal of Human–Computer Studies
(1995) - et al.
The role of the non-anticipativity constraint in commercial software for stochastic project scheduling
Computers and Industrial Engineering
(1996) - et al.
Stochastic network project scheduling with non-consumable limited resources
International Journal of Production Economics
(1997) - et al.
A heuristic for network project scheduling with random activity durations depending on the resource allocation
International Journal on Production Economics
(1998) - et al.
Fuzzy project scheduling system for software development
Fuzzy Sets and Systems
(1994) - et al.
Fuzzy priority heuristics for project scheduling
Fuzzy Sets and Systems
(1996) - et al.
The construction of stable project baseline schedules
European Journal of Operational Research
(2004)
Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines
European Journal of Operational Research
Activity time-cost tradeoffs under time and cost chance constraints
Computers and Industrial Engineering
Sensitivity analysis of scheduling algorithms
European Journal of Operational Research
Analysis of reactive scheduling problems in a job shop environment
European Journal of Operational Research
On the optimal management of project risk
European Journal of Operational Research
Using tabu search to schedule activities of stochastic resource-constrained projects
European Journal of Operational Research
A fuzzy project scheduling approach to minimize schedule risk for product development
Fuzzy Sets and Systems
A fuzzy robust scheduling approach for product development projects
European Journal of Operational Research
One machine rescheduling heuristics with efficiency and stability as criteria
Computers and Operations Research
The shifting bottleneck procedure for job shop scheduling
Management Science
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
Match-up scheduling with multiple resources, release dates and disruptions
Operations Research
A new method for workshop real time scheduling
International Journal of Production Research
Characterization of a set of schedules in a multiple resource context
Journal of Decision Systems
Criticality in resource constrained networks
Journal of the Operational Research Society
Scheduling independent tasks to reduce mean finishing time
Communications of the ACM
Planning and re-planning in project and production planning
Omega
Metaheuristic technique for solving multiobjective investment planning problem
Control and Cybernetics
β-robust scheduling for single-machine systems with uncertain processing times
IIE Transactions
Robust scheduling to hedge against processing time uncertainty in single-stage production
Management Science
RanGen: A random generator for activity-on-the-node networks
Journal of Scheduling
Project Scheduling––A Research Handbook
Probe backtrack search for minimal perturbation in dynamic scheduling
Constraints
Understanding simulation solutions to resource-constrained project scheduling problems with stochastic task durations
Engineering Management Journal
Scheduling tasks with and/or precedence constraints
SIAM Journal on Computing
Critical Chain
Cited by (805)
A branch-and-bound algorithm for the proactive resource-constrained project scheduling problem with a robustness maximization objective
2024, Computers and Operations ResearchA chance-constrained optimization approach integrating project scheduling and material ordering to manage the uncertain material supply
2024, Computers and Operations ResearchA target-time-windows technique for project scheduling under uncertainty
2024, European Journal of Operational ResearchEfficient optimal Kolmogorov approximation of random variables
2024, Artificial IntelligenceA trapezoidal intuitionistic fuzzy optimization approach for crashing a budget constrained project
2024, Ain Shams Engineering JournalDeveloping a national pandemic vaccination calendar under supply uncertainty
2024, Omega (United Kingdom)
- 1
The work was performed while the second author was Research Assistant of the Fund for Scientific Research, Flanders (Belgium) (F.W.O.).