Project scheduling under uncertainty: Survey and research potentials

Abstract

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.

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.