Project scheduling problems (PSP) could be defined as allocating scarce resources over time to perform a given set of activities. The resources are arbitrary although constituting a necessary means which activities compete for. Notion of the activity can have a variety of interpretations. Thus defined project scheduling problems appear in a large spectrum of real-world situations, and, in consequence, have been intensively studied by specialists in management science, operations research and computer science.

In this chapter the brief history of the deterministic project scheduling models (formulations) is presented in Sect. 3.1. Section 3.2 review basic models for the Resource-Constrained Project Scheduling Problem (RCPSP) as well as their classification. Finally, in Sect. 3.3 some special cases of the RCPSP are mentioned as a short review of its big family. Examples of most commonly used objective functions are presented in Sect. 3.4.

1 Historical Review

The first models and methods for deterministic project scheduling date back to the 1950s when the well known network-based models like critical path method or project evaluation and review technique were formulated and developed. Critical Path Method (CPM) [1, 2] is based on mathematical model which determines the sequence of project activities for projects with ordinary precedence constraints. In Metra Potential Method (MPM) [3] generalized precedence constraints are considered. Project Evaluation and Review Technique (PERT) [4] focuses on creating and controlling project schedules in stochastic environments using deterministic or probabilistic activity processing times. Although the network-based models have proved useful in handling scheduling for various projects, they simplified the problems by assuming that the availability of resources is not limited, which is unrealistic in majority of practical situations. Beginning in the late 1960s, the models were extended by additionally considering scarcity of resources, see for example [5, 6]. The impact of limited resources on project characteristics started to be taken into account in such models as CPM/MCX (Minimum Cost eXpediting) or CPM/resources. Graphical Evaluation and Review Technique (GERT) [7], in turn, allows loops between activities and additionally takes probabilistic precedence relations into account. These problems and models are usually referred to as the resource-constrained.

Since then, interest and research efforts in the field of resource-constrained project scheduling have increased, and many new models and methods have been developed. Overviews of the advances in models and solution methods are given in the survey papers of Icmeli et al. [8], Elmaghraby [9], Özdamar and Ulusoy [10], Herroelen et al. [11], Brucker et al. [12], Kölisch and Padman [13], Dorndorf [14], Artigues et al. [15] or Węglarz et al. [16].

2 Basic Models and Classifications Review

Most of the early studies on RCPSP relate to mathematical programming formulation and its relaxation used in B&B (branch-and-bound) approaches [17, 18]. However, solving the linear programming relaxation of any model of the RCPSP is too time consuming, or just impossible, in practical applications [15]. The RCPSP can be formulated as a mathematical programming model in several ways, depending on the definition of the decision variables and constraints construction.

The main mathematical programming formulations and their relaxations proposed for the classical RCPSP can be divided into two main classes [15]:

  • sequence/order-based models,

  • time-indexed/discrete-time integer linear programming models.

The first class concentrates on ordering, the sequence activities are processed one after another. The second class concentrates on assigning resources to activities at each point of time.

In the sequence based mathematical programming models scheduling can be viewed as determining a sequence of activities satisfying the precedence constraints, and then fixing the processing times of activities following such sequence and respecting other possible constraints. In the time-indexed models problem formulations are based on time discretization which naturally describe the usage of the resources and the processing of the activities over time. In these models the fixed planning horizon, denoted by H, is required. It means that all activities have to be completed by time H.

In recent years different classifications for the RCPSP have been proposed and used, and new models have appeared. Reviews and propositions of the new models can be found for example in the papers of Koné et al. [19, 20], Artigues [21], and Kopanos et al. [22].

The RCPSP models are formulated as:

  • Binary Integer Programming (BIP),

  • Mixed Integer Programming (MIP),

  • Mixed Integer Linear Programming (MILP).

In binary formulation, each variable can only take on the value of 0 or 1. In the RCPSP binary variables are usually used to indicate whether one activity is processed before the other or whether an activity finishes (or starts) at fixed time point or not. In the MIP formulation some of the variables are real-valued and some of the variables are integer-valued. When the objective function and constraints are all linear, it is called MILP.

RCPSP models could be also classified as:

  • Discrete-Time (DT),

  • Continuous-Time (CT).

In DT models time-indexed binary decision variables are used. Hence, schedule events can only take place at a certain predefined time points. In such models the time horizon is divided in uniform time intervals. In CT models for the RCPSP, binary variables indicate the processing sequence between pairs of activities, hence rely on precedence-based decision variables. In such models schedule events can occur at any time in the time horizon of interest. Time-indexed CT models can be derived, if a variable time grid is used.

Several time-indexed DT BIP models were proposed for the RCPSP. One of the first such model, where one linear constraint for each time period is formulated to avoid resource conflicts, was proposed by Pritsker et al. [17] (see Sect. 4.1). It is called basic discrete-time (DT) model. Very similar formulation, called disaggregated discrete-time (DDT) formulation was proposed by Christofides et al. [23]. The mainly difference is in the precedence constraints formulation.

Similar model, based on the notion of the feasible set of activities, was proposed by Mingozzi et al. [24]. Additionally, they derived lower bounds from this formulation by relaxing the non-preemption and the precedence constraints to disjunctions and time-windows. The relaxation is applied to calculating lower bounds for different scheduling problems.

Klein [25] adopted to the classical RCPSP a DT BIP formulation proposed for preemptive version of the RCPSP by Kaplan [26], where a single type of binary variables that specifies whether activity is active over time period or not was introduced, as well as a simpler definition of the resource-constraints. Klein [25] proposed two additional models for the RCPSP. The first is based on the definition of binary variables which specify if an activity starts at the beginning of fixed time period or earlier. In the second model a different range for the above mentioned binary variables and a new binary variables, that denote whether an activity is completed at the end of fixed time period or earlier, were introduced.

Artigues et al. [27] proposed a formulation called Flow-based Continuous-Time (FCT) model. It is based on the notation of resource flow, where three types of variables are used: starting time variables for each activity, sequential binary variables indicating whether one activity is processed before the other, and flow variables denoting the quantity of resource that is transferred between activities.

The hybrid between a sequence-based model and Mingozzi’s relaxation mathematical programming model was proposed by Carlier and Néron [28, 29].

Several CT MIP models were proposed for the RCPSP. One of the first, based on minimal forbidden (resource incompatible) sets and sequence of activities, was proposed by Alvarez-Valdez and Tamarit [30]. These sets contain activities that have no precedence relations between them and cannot be executed simultaneously due to resource availability. It is a natural extension of the linear ordering approach for disjunctive scheduling. In this model binary variables define the sequencing of activities, and integer variables represent the starting time of each activity.

Koné et al. in [19] proposed two event-based CT MIP models based on the concept of event: the Start/End and On/Off formulation. In these models the decision variables are indexed using event points (instead of time points) that correspond to the start or end times of activities. The scheduling horizon is subdivided into intervals of variable length. An event means the beginning of the interval when the activity starts. Each activity starts at a unique event and the starting time of the activity equals the starting time of the assigned event. In the Start/End Event-based Model (SEE) two sets of binary variables and two types of the continuous variables are used. Binary variables describe the activity starts and ends at any event point. Continuous variables represent the date of event and the quantity of resources required immediately after the event. In the On/Off Event-based Model (OOE) only one type of binary variable per event, and one type of continuous variable are used. The binary variable denotes whether the activity starts processing at the event point or it is still being processed immediately after this event. The continuous variable represents, as in SEE, the date of event. In this model, the number of events is exactly equal to the number of activities.

Bianco and Caramia [31] proposed a DT MIP formulation based on the definition of one type of the continuous variable that represents the percentage of the activity that is executed at each time interval. Two types of binary variables represent whether the activity starts and ends at the time interval.

Recently, Kyriakidis et al. [32] proposed a time-indexed CT MIP formulation for single- and multi-mode RCPSP. It is based on the Resource-Task Network (RTN) representation. RTN is a network representation technique, used in process scheduling problems, based on the continuous time models.

Moreover, Kopanos et al. [22] proposed two DT MILP models and two CT MILP models. The DT models are based on the definition of binary variables that describe the processing state of every activity between two consecutive time points, The continuous-time models are based on the concept of overlapping of activities, and the definition of a number of newly introduced sets.

The other classical representation, as well as method of solving the RCPSP is based on the constraint programming. The classical RCPSP was formulated as a constraint-based scheduling approach, using the Optimization Programming Language (OPL), by Van Hentenryck [33].

3 Generalizations and Special Cases of the RCPSP

While the RCPSP is already a powerful model, it does not cover all situations that occur in practice. On the other hand, RCPSP model is commonly used in a variety of engineering fields. Hence, many scheduling problems can be formulated as the special case of the RCPSP, such as job-shop scheduling, flow-shop scheduling, open-shop scheduling and project scheduling [34]. Therefore, many more general project scheduling models have been developed together with extensions and variants of the RCPSP such as well known MRCPSP, MSPSP, RCPSP/max, MRCPSP/max, or MRCMPSP.

The MRCPSP (Multi-mode Resource-Constrained Project Scheduling Problem) is a generalization of the RCPSP where several modes of execution may exist for any activity of the project. The problem is considered in Sect. 5. In this model also the renewable and non-renewable resources are considered.

An example of special case of the MRCPSP is the Discrete Time/Resource Tradeoff Problem (DTRTP) where only one single renewable resource with fixed capacity is given (e.g., modeling available staff).

The MSPSP (Multi-Skill Project Scheduling Problem) was proposed by Néron and Baptista [35] to model project scheduling problems in IT companies. In this extension, resources correspond to persons that master a subset of skills required by the different activities of the project.

The RCPSP/max (RCPSP with minimum and maximum time lags), known also in the literature as the RCPSP with time windows or RCPSP with Generalized Precedence Relations (RCPSP-GPR), involves generalized precedence relations (temporal constraints) of the start-to-start type where the minimum and maximum time lags between activities are considered. The MRCPSP/max is generalization of the RCPSP/max, MRCPSP and RCPSP.

The MRCMPSP (Multi-mode Resource-Constrained Multi-Project Scheduling Problem) is a generalization of RCPSP and MRCPSP where additionally multiple projects are considered [36]. The MRCMPSP consists of a number of projects, defined as collections of activities performed in one of several ways under given precedence relationships and limited amounts of various types of resources.

In the RCPSPVRL (Resource-Constrained Project Scheduling Problem with Varying Resource Levels) resources of limited availability but varying predetermined levels are used. In this problem project activities are not assumed to have constant resources throughout the entire project duration. In RCPSPVRL, resources are not constant throughout the entire project duration. The total project duration is divided into different time periods. Within a particular time period quantity of resources can vary in various time periods.

4 Objective Functions

The objective of the basic PSP model is time minimization, however the resource, cost or quality related objectives are also commonly used, especially in practical applications. For example: the resource-based objective functions are considered in the area of resource investment problems (RIP), resource leveling problems (RLP) and time/resource trade-off problem (TRTP); the cost-based objective functions in the area of time/cost trade-off problems (TCTP) and payment scheduling problems (PSP).

In this part of the book the total length of the schedule minimization is considered, which is the most commonly used objective function in the project scheduling. The total length of the schedule is also called project duration, project complexion time, or makespan.

The other commonly used objective functions include, for example:

  • total flow time,

  • weighted (total) flow time,

  • maximum lateness,

  • total tardiness,

  • total weighted tardiness,

  • number of late activities,

  • weighted number of late activities,

  • net present value (NPV).

In case of optimizing one criterion only the single objective optimization problems are considered. If there are more than one criterion which must be treated simultaneously, the multiple objective optimization problems must be taken into account. The models for multiple objective project scheduling were considered, among others, by Davis [37] and Ishii [38].