Handling Alternative Activities in Resource-Constrained Project Scheduling Problems

1 Introduction

Disruption management (DM, see [Yu and Qi, 2004; Clausen et al., 2001]) is the process of responding to an unforeseen disturbance occurring during the execution of planned and scheduled operations. It is aimed at the selection of appropriate repair actions which help to get back on track and to minimize the negative impact typically associated with a disruption. Two forms of interventions can be distinguished:

• Rescheduling corresponds to a shift of scheduled starting times or a change in the allocation of resource entities to activities. It is particularly relevant in domains where the set of operations is fixed and no process variability is given: Production processes form a typical example.
• A process variation corresponds to the switch from a previously chosen process variant to another one. This form of modification is applied in many practical domains to insert or remove activities, to change execution orders, etc.: For example project scheduling and supplychain management are typically characterized by the existence of various predefined process variants.

The Resource-Constrained Project Scheduling Problem (RCPSP, see [Błazewicz et al., 1983; Brucker et al., 1999]) provides a generic and well-established framework for the formal description of scheduling problems: Generalizing the production-specific job shop, flow shop and open shop problems, it imposes no restrictions on either the number of entities per resource type, the way activities are connected or the characteristics of resource requirements. Moreover, the existence of various highly efficient algorithms for its solution (see [Kolisch and Hartmann, 2005]) proves that the RCPSP has been and still is an area of intensive research.

The rescheduling part of DM problems can be solved within the framework provided by the RCPSP. As regards potential process variations, however, there exist no possibilities to describe alternative execution paths within the RCPSP: It is thus impossible to overcome a previously made decision on a certain process variant during optimization. To the best of our knowledge, the only approach to more flexibility has been made in the Multi-Mode RCPSP (MRCPSP, see [Hartmann, 2001] for example): Through the definition of various execution modes per activity, it is possible to consider changes in their durations and associated resource requirements. But it is obvious that the concept of mode alternations is not sufficient for the description of the entire range of potential variations.

Research on DM in the context of the RCPSP has mainly focused on responding to disruptions by way of rescheduling: Artigues et al. [2003] propose an approach to insert an unexpected activity into a given schedule; Elkhyari et al. [2004] use explanations to cope with over-constrained networks in dynamic scheduling problems; Zhu et al. [2005] present a hybrid mixed integer programming/constraint propagation approach to handling various classes of disruptions. In contrast to these works, which all focus on mere rescheduling, we herein extend the scope of available options by making switches between different process variants possible.

For this purpose, we propose to extend the RCPSP by the concept of alternative activities: In Section 2, the formal description of the conceptual extension and a modeling example from the domain of air traffic management are provided. In Section 3, we propose a novel genetic algorithm (GA) for the solution of the problem: The specific crossover and mutation operators are discussed as well as the promising results of a detailed evaluation. Finally, Section 4 summarizes the contributions of this paper.

2 AConceptual Extension of the RCPSP

2.1 Alternative Activities

We base our approach to defining alternative execution paths on the concept of alternative activities and activity dependencies. The expressive power of these constructs is illustrated by several modeling examples of typical process variations:

• A mode alternation corresponds to a change of the duration and the resource requirements associated with an activity. Basically, each execution mode can be represented by a separate alternative activity. If, for example, in a sequence a, b and c three modes of b shall be distinguished, the alternative activities b1, b2 and b3 can be considered instead of b.
• For the dynamic insertion/removal of activities, the possibility to describe activity dependencies is required: An activity i is considered dependent on another activity j, if j has to be executed whenever i is scheduled. If, for example, it shall be possible to dynamically insert an activity e into a sequence a, b and c, it is sufficient to consider two alternatives of an arbitrary scheduled operation (activity b, for example): One variant (b1) is dependent on the execution of e whereas the other one (b2) is not.
• A potential order change can be described by alternative versions of all involved process steps: One variant represents the original, the other one the optional position of the activity. If, for example, it shall be possible to swap b and d in a sequence a, b, c and d, b1 and d1 correspond to the original, b2 and d2 to the alternative positions.
• The serialization/parallelization of operations is based on two alternative activities with different precedence relations associated: One variant is a predecessor of another activity whereas the other one is not. If, for example, it shall be possible to parallelize b and c in a sequence a, b, c and d, it suffices to consider two versions of b: b1 is a predecessor of c and represents the option of serial execution, whereas b2 is not necessarily scheduled before c and represents the option of parallel execution.

By applying the concept of alternative activities, both parts of the DM problem - the selection and scheduling of operations - are combined in one single conceptual model. This implies that (1) no detached process definitions need to be synchronized and that (2) particularly efficient algorithms can be applied for problem solving [Bart´ak, 1999].

2.2 The Extended Resource-Constrained Project Scheduling Problem

As regards the consideration of alternative activities in scheduling problems, little research has been done so far. One of the most important approaches can be found in the area of constraint-directed scheduling: Beck and Fox [2000] base their work on the introduction of XOR-nodes as well as PEX (Probability of Existence) variables into the constraint graph, and propose specific, PEX-based propagators and heuristics for solving such extended problems.

In contrast to their work, which aims at extending the scope of constraint-directed scheduling approaches, our goal is to incorporate the concept of alternative activities into the framework of the RCPSP. Consequently, we propose a compact and intuitive way of modeling process execution variants which is independent from the underlying search procedure: In the Extended Resource-Constrained Project Scheduling Problem (x-RCPSP), the concept of alternative activities is implemented through the distinction between active and inactive activities: Only the former ones are actually considered in the resulting schedule. By activating and deactivating activities it is possible to change the activation state of the model. Note that each potential combination of active elements forms an individual instance of the classical RCPSP: It is thus possible to apply well-established methods for activity sequence optimization.

Formally, the x-RCPSP can be described as follows. A process is composed of a set of potential activities A 0, 1, ..., a, a 1 where the first and the last element represent abstract start and end activities: They have a duration of 0 and do not require any resources. Each remaining i A has a non-negative duration di assigned. Active activities are grouped in a subset A A , inactive activities are contained in the set difference A A. For the execution of activities, a set of renewable resource types R 1, ..., r is available: For each type k R, there exists a constant amount of ck units. Various forms of activity dependency can be described by use of the following constructs:

• Precedence Constraints. The order of activities is described by use of precedence constraints: The existence of pi,j states that activity i A has to be finished at or before the start of j A . In accordance with the distinction between active and inactive activities, P contains all potentially relevant constraints whereas P pi,j P i, j A groups only relations in which predecessor and successor are currently active.
• Resource Requirements. Resource requirements describe the relation between activities and resources. Activity i A requires a constant amount of qi,k units of resource type k R throughout its execution. Again, two sets are distinguished: Q contains all potentially relevant dependencies whereas Q qi,k Q i A groups only the requirements of active activities.

Potential activation state modifications and associated dependencies are described by use of the following constructs:

• Activity Substitutions. If xi,j is contained within the set of potential activity substitutions X , it represents a legal form of process variation to activate j A A for the deactivation of i A: j replaces i within A.
• Activity Dependencies/Constraints. Since the activation or deactivation of an activity might have an impact on the state of other activities, M describes dependencies between the elements of A : mi,j (mi,j ) M indicates that activity j A has to be (de)activated upon the (de)activation of i A ; mi,j M indicates that j has to be deactivated upon the activation of i, and mi,j M indicates that j has to be activated upon the deactivation of i. Note that these constraints have to be defined carefully in order to avoid inconsistencies.

The presented x-RCPSP is a generalization of the MRCPSP, which itself generalizes the classical RCPSP [Hartmann, 2001]: Any MRCPSP can be formulated as an x-RCPSP. As regards the formulation of an x-RCPSP as an MRCPSP, the limitations of MRCPSPs must be observed. Such a formulation which preserves the activities, precedence constraints and resource constraints of the x-RCPSP is possible if the following properties hold:

(1) It is not possible to describe one-directional mode substitutions in the MRCPSP. (2) Any activity execution mode has always to be a direct substitute of all other ones. (3) Activity replacements are only possible at exactly the same position: No changes of the activity execution order can thus be defined. (4) No activity dependencies can be described for different execution modes: It is therefore not possible to dynamically insert or remove activities.

The result of solving the x-RCPSP is a combination of model activation state and sequence of all active activities: A schedule S is represented as a vector of starting times β1, β2, ..., βn for the set of active activitiesAwith A n. S is considered valid if the following criteria are fulfilled:

• Activation State Validity. The activation state A associated with a schedule S is valid, if and only if it can be derived from an original valid activation state through the application of the substitutions defined in X , satisfying all constraints defined inM .
• Starting Times Validity. Let A t be the set of activities carried out at a time t. The staring times β1, ..., βn are valid if (1) βi 0 for any i A, (2) βi di βj for any pi,j P and (3) i A t qi,k ck for any k R at any t. Note that these criteria correspond to the ones defining schedule validity in the context of the RCPSP.

2.3 Modeling an Exemplary Process

In this section it is illustrated how the framework of the x-RCPSP can be applied for the formal description of realistic processes. For this purpose, the aircraft turnaround - as the process aircrafts typically go through at an airport between touchdown and takeoff - is considered in a simplified version (corresponding to the combination of core processes as defined by [Carr, 2004]): After the plane reaches its final position, incoming passengers leave the aircraft (deboarding). It is then prepared for the next flight during fueling, cleaning and catering, which may be executed simultaneously. Outgoing passengers enter the aircraft (boarding) before the plane finally leaves its position heading for the runway.

Apart from inherent options of rescheduling, three forms of variations are assumed to be available for the adaptation of the process in response to disruptions: First, deboarding can be accelerated through the assignment of additional buses. Second, cleaning can be shortened if in exchange the cabin

Table 1: x-RCPSP Description of the Aircraft Turnaround

Set Content

• R Bus, Firebrigade
• A Start, Deb, DebB , Fue, FueP , Cat, Cle, CleR, Ins, Boa, End
• P Start Deb, Start DebB , Deb Fue, Deb FueP , Deb Cat, Deb Cle, Deb CleR, DebB Fue, DebB FueP , DebB Cat, DebB Cle, DebB CleR, Fue Boa, FueP End, Cat Boa, Cle Boa, CleR Ins, Ins Boa, Boa End
• Q Deb ▷ 1 Bus, DebB ▷ 2 Bus, FueP ▷ 1 F irebrigade
• X Deb DebB , Fue FueP , Cle CleR
• M CleR Ins, CleR Ins

is inspected by the cabin crew prior to boarding. And third, the process can be accelerated by parallelizing fueling and boarding if the fire brigade is present for supervision.

Table 1 summarizes the central elements of the corresponding x-RCPSP (particularly activity durations and resource capacities are omitted) based on a simplified form of notation: (1) i j stands for pi,j, (2) i▷n k for qi,k n, (3) i j for xi,j , (4) i j for xi,j xj,i, (5) i j for mi,j , etc. Process steps are represented by the first three letters of the associated activity names. Potential process variations are expressed by use of alternative activities. The first of the available options corresponds to a mode alternation (as also possible in an MRCPSP): DebB is characterized by reduced time and additional resource requirements. The second option corresponds to a combination of mode alternation and activity insertion: CleR takes less time but is connected to the optional activity Ins (for cabin inspection). The third option corresponds to the parallelization of two process steps: FueP is not necessarily executed prior to boarding but has additional resource requirements associated.

3 Solving the x-RCPSP

The application of the x-RCPSP to DM is based on a comprehensive model describing the baseline schedule and all valid process variants. The following steps are performed upon the occurrence of a disruption: (1) The schedule is updated accordingly. (2) Based on a schedule evaluation function f S and the corresponding objective (minimization or maximization), optimization is performed. Unlike in scheduling problems, where mainly the minimization of the total process execution time (the so-called makespan) is of interest, common goals in DM are the minimization of costs for earliness, tardiness, interventions and the deviation from the original schedule: Typically, several of these aspects are combined. (3) Finally, the difference between the original and the optimized schedule is interpreted as the set of interventions to apply.

Due to the central relevance of the second step, we will focus on the optimization of the x-RCPSP in this section. As regards the choice of an approach to the identification of the optimal combination of activation state and activity starting times, the mentioned practical relevance of proximity to the original schedule suggests the use of incremental local search algorithms. Since, moreover, performance usually represents a crucial factor in the operative process of DM and since particularly genetic algorithms perform well for the RCPSP [Kolisch and Hartmann, 2005] we herein present and evaluate an evolutionary algorithm for the solution of the x-RCPSP.

3.1 An Evolutionary Algorithm

Representation

Due to the complexity associated with the direct modification of time values, it is a common approach to use some sort of abstract solution representation during optimization [Kolisch and Hartmann, 2005; Hindi et al., 2002]. We decided on the use of activity lists: λ is a precedence feasible list of all elements in A, describing the order in which active activities shall be added to the schedule. In the associated serial schedule generation scheme, each operation is scheduled at the earliest possible time: This way, each valid λ can be converted into a valid schedule unambiguously.

Initialization

The original schedule can be converted into a corresponding activity list easily: λ0 is obtained by simply sorting all active activities by their scheduled starting times. It represents the legal option of performing no intervention at all and is therefore considered the first element of the first generation. All other solutions of the initial population are generated by the application of the mutation operator (see below) on λ0.

Crossover

If the elements contained in two parent activity lists λa and λb are equal, one of the well-elaborated RCPSP-specific crossover operators can be applied (see [Hartmann, 1998; Hindi et al., 2002] for examples or [Kolisch and Hartmann, 2005] for a comprehensive overview). If, however, the contents of λa and λb differ, list combination is more difficult: Algorithm 1 summarizes a crossover operator, which is based on the idea that λa steers the selection of elements contained in the child whereas λb determines the respective order, and which guarantees that only valid activity lists are generated.

Algorithm 1 Crossover (λa, λb)

1: if Aa Ab then 2: apply RCPSP-specific crossover operator 3: else 4: T Xa Xb xi,j X xj,i Xb Xa 5: if T Xa△Xb then return incompatible 6: λ λb 7: do 8: changed false 9: if i λ, xi,j T then 10: replace i with j in λ 11: changed true 12: end if 13: while changed 14: end if 15: return λ

Algorithm 2 Mutate (λ)

1: if a randomly generated value 0, 1 θ then 2: rearrange λ by applying RCPSP-specific mutation 3: else 4: select an arbitrary xi,j X i λ 5: replace i with j in λ 6: end if 7: return λ

Denoting the set of activities in λi as Ai A , it is first checked whether an RCPSP-specific operator can be applied (line 1). If this is not possible due to Aa Ab, a transition set T X is initialized for coping with different list contents: T describes which substitutions have to be applied for the conversion of λb to λa. Let Xi X be the set of substitutions that has led from an original set A0 to Ai: T can then be defined as the combination of all substitutions exclusive to λa and the inversion of all substitutions exclusive to λb (line 4). Since, however, substitutions are not necessarily directly reversible, it might be the case that λb can not be (directly) transformed into λa: If the size of T is unequal to the size of the symmetric difference Xa△Xb, the activity lists are considered incompatible for crossover and a different selection of parent lists has to be made (line 5). Otherwise, the child activity list λ is initialized as a clone of λb before a repetitive replacement procedure is started (line 7 to 13): As long as λ contains replaceable elements in terms of T , the respective substitutions are applied: Note that dependencies in M have to be observed and that precedence feasibility has to be secured by shifting successors to the right-hand side of their predecessors. If the application of the substitutions in T results in an inconsistency (i.e. activities have to be activated and deactivated at the same time due to contradicting dependencies inM ), the replacement operator (called in line 10) fails: λa and λb are considered incompatible for crossover and different parent activity lists have to be selected.

If, for example, λa DebB , Fue, Cle, Cat, Boa and λb DebB , Cat, CleR, Ins, Boa, FueP for the process modeled above, the transition set T CleR Cle, FueP Fue can be deduced fromXa DebDebB and Xb Deb DebB, Cle CleR, Fue FueP . Crossover thus results in λ DebB , Cat, Cle, Fue, Boa .

Mutation

An x-RCPSP-specific version of the mutation operator is described in Algorithm 2: Apart from changes in the order of activities, also potential process variations are considered.

With a certain probability θ, the activation state is left unmodified and any RCPSP-specific mutation operator can be applied for the randommodification of λ (see the references mentioned above for crossover). Otherwise, an arbitrary replacement is selected for an element contained in the activity list: As regards its application, again all associated dependencies and precedence constraints have to be observed.

Fitness and Selection

The quality of an activity list is evaluated by converting it into the corresponding schedule and analyzing the associated costs by use of the predefined schedule evaluation function.

This way, activity lists are made comparable. In each step of evolution, a new generation is derived from the previous one by combining the best individuals (the survivors) with new ones (their children) generated through the application of crossover and mutation to the fittest activity lists. In order to avoid the convergence to a local optimum, we randomly replace individual members of the generated population with the initial activity list λ0: The probability for such replacements is decreasing with the continuing progress of evolution. Due to the significant role of randomness in the selection and mutation of solutions, it is made sure that the exact optimum is identified by the GA at least within an infinite time horizon.

3.2 Computational Experiments

The above algorithm has been implemented in a Java-based rescheduling engine: The realization of the RCPSP-specific operators is based on the GA proposed by Hartmann [1998]. As there are currently neither instances of nor testset generators for reactive scheduling problems available [Policella and Rasconi, 2005], a framework for the parameterized generation of DM problems has also been developed: Normalized versions of network complexity, resource factor and resource strength (as proposed by Kolisch et al. [1995]) as well as parameters describing the characteristics of baseline schedules and disruptions can be used to define the problem structure.

The generated instances consist of a baseline schedule and a disruption occurring during its execution. Based on the possibility to assign a due date δi to an activity i A , the goal of optimization is to minimize the sum of the overall process tardiness i A max 0, βi di δi and the number of schedule modifications: Each modification is assumed to cause three times the costs of one time unit of tardiness.

As regards complexity aspects, the following configurations have been used to generate 16 different problem classes:

• Low/High Process Complexity. Based on this parameter it can be specified whether the scheduled activities are linked by few or by many precedence constraints.
• Low/High Resource Complexity. The aspects of resource requirements and resource availability are combined in this parameter: Low resource complexity corresponds to the existence of few requirements and the availability of many resource entities, high complexity to the opposite.
• With/Without Left-Shifts. If an activity is scheduled to start earlier than it did in the original schedule, this is considered a left-shift. Whether such modifications are valid or not can be defined by the assignment of appropriate lower bounds to the activity starting times.
• Tight/Wide Baseline Schedule. The distribution of starting times and the amount of incorporated slack time are combined in this parameter: In a tight (wide) schedule, activities (do not) start at the earliest possible point and many (only few) processes are executed simultaneously.

Small and large problem instances were distinguished: The former consist of one process containing 10, the latter of one process containing 100 activities. For each problem class, 10 instances of both sizes were generated by random; on average, one out of ten activities had one of the execution alternatives mentioned in Section 2.1 associated. In each case, a disruption was injected immediately at the start of execution by doubling the durations of half the activities.

As there is currently no benchmark data available for DM problems, it was not possible to compare the proposed GA to existing approaches. Instead, the fast convergence of schedule quality towards the optimal or at least a good solution is illustrated. Table 2 summarizes how much of the identified optimization potential could be tapped within limited time 1 .

For each of the small instances, first the exact optimumwas identified based on a deterministic procedure: The difference between the costs associated with the disrupted schedule SΔ and the optimal schedule S defines the optimization potential. For the evaluation of the GA, 10 runs were conducted for each of the generated cases and each of the regarded time limits: Let S denote the schedule resulting fromsuch limited optimization. The figures listed in Table 2 thus correspond to the average value of f SΔ f S f SΔ f S : Basically, they reveal that in almost any case the optimum could be identified already within the first 5 or 15 seconds of optimization.

As even by use of the most powerful exact methods (see [Laborie, 2005] for a recent approach) hard scheduling problems of the considered size are not tractable in reasonable time [Hartmann, 1998; Alcaraz et al., 2003], an alternative procedure has been chosen for the large instances. Instead of identifying the actual optimum, the best solution that could be found during (1) all GA runs and (2) an additional run limited to 10 minutes was taken as a reference. This approach was motivated by the observation that large improvements can mainly be made within the first generations: The typical development of the costs associated with the best known schedule throughout 10 minutes is depicted in Figure 1. Correspondingly, the figures listed in Table 2 show how close the GA could get to the best known solution within 5, 15 and 45 seconds. The following observations can be made:

1 The used problem instances and more detailed evaluation results can be obtained from http://rcpsp.serverside.at/ijcai-07.html

• Due to the fact that the existence of many precedence constraints narrows the search space, the GA converges faster for problems with high process complexity.
• Resource complexity has considerable impact on the time required for the conversion of activity lists into schedules. A low complexity value thus means that more schedules can be analyzed within the available time and that the GA converges faster, therefore.
• The possibility of left-shifts extends the space of available rescheduling options: The genetic algorithm performs better if only activity postponements are valid.
• The aspects of slack time and process simultaneity have no significant impact on the speed of convergence.

The overall values indicate that the assumption of fast convergence to good schedule quality holds. Although no comparison with existing algorithms was possible (due to the mentioned lack of comparable results), the figures illustrate the effectiveness of the proposed operators and represent a starting point for future improvements and evaluations: Our recent results indicate that particularly local forms of rescheduling can improve the algorithm's efficiency.

4 Conclusions

This paper described how the generic framework of the RCPSP can be extended by the concept of alternative activities, to make its application in realistic DM problems possible: The x-RCPSP is based on a distinction between active and inactive activities as well as the definition of valid activity substitutions and associated constraints. Beside the modeling framework, we presented a novel genetic algorithm for the solution of the proposed generalization of the RCPSP. Its evaluation (which was based on an additionally published set of problem instances) proved the fast convergence of schedule quality towards the optimal or at least a good solution.

Acknowledgments

This research project was partly funded by grants from (1) FFF Austria, Project cdm@airports, and (2) the European Union, Project WS-Diamond, Contract 516933.