Local Rescheduling - A Novel Approach for
Efficient Response to Schedule Disruptions

This page provides detailed information on the computational experiments described in [1]: Both the regarded problem instances (i.e. three sets of instances of the Extended Resource-Constrained Project Scheduling Problem, x-RCPSP, see [2] for a detailed description) and the respective results are available for download. The former can be used for the further evaluation and comparison of related algorithms, the latter illustrate the high efficiency of the presented Local Rescheduling (LRS) procedures.

Problem Instances

As regards the testsets used for performance evaluation, each of the ZIP files provided above contains 160 XML files describing 10 problem instances of each of the 16 regarded problem classes. The XML file name contains two numeric segments. The first one describes the problem class in a binary format: The first digit stands for low(0) or high(1) process complexity, the second digit stands for low(0) or high(1) resource complexity, the third digit defines whether(0) or not(1) left-shifts are allowed and the last digit stands for tight(0) or wide(1) baseline schedule. The second numeric segment in the file name is the case's running number. As regards the structure and the content of the XML descriptions, the following annotations can be made:

1. ResourceDefinition: This element contains various resource type definitions.
   • ResourceType: Describes that amount units of a resource type identified by id and the descriptive name name are available. The element may contain several definitions of resource unavailability.
     • Unavailability: States that amount units of the containing resource type are unavailable for duration time units, starting at start.
2. ProcessDefinition: This element contains various process type definitions.
   • ProcessType: Describes a process type identified by id and the descriptive name name. A process is defined by activities, associated precedence constraints, resource requirements, activity substitution rules and constraints.
     • Activity: Describes an activity identified by an id and a descriptive name name. The duration describes how long execution lasts by default. An activity is contained in the baseline schedule if active is set to true.
     • Precedence: Describes a precedence constraint linking two activities. The activity identified by suc must not start prior to the end of pre.
     • Requirement: Describes a resource requirement associated with an activity. The activity identified by activity requires amount units of resource type resource throughout its execution.
     • Alternative: Describes an activity substitution rule. It represents a legal form of process variation to activate is upon the deactivation of of.
     • Dependency: Describes a constraint between the activation state of two activities. The activity identified by lhs is on the left-, the one identified by rhs is on the right-hand side of the respective relation. The type of relation is defined by rel, for which the following values are currently supported:
       • ActivatesUponActivation: Activity rhs is activated whenever activity lhs is activated.
       • ActivatesUponDeactivation: Activity rhs is activated whenever activity lhs is deactivated.
       • DeactivatesUponActivation: Activity rhs is deactivated whenever activity lhs is activated.
       • DeactivatesUponDeactivation: Activity rhs is deactivated whenever activity lhs is deactivated.
3. InstanceDefinition: This element contains the definitions of planned process instances and particular activity properties.
   • Instance: Describes that an instance of the process type type is intended to start at start. The instance, which is identified by id and the descriptive name name, shall be completed before due.
   • Activity: Can be used to describe and override properties of an activity contained in the defined instances: For an activity identified by id (which consists of the ID of the containing process and the ID of the considered activity, separated by a dot) the planned starting time start and the duration property can be overwritten.
   • Precedence: Can be used to define additional (and particularly inter-process) precedence constraints between two activities pre and suc.
4. DisruptionDefinition: This element contains the definitions of the disruptions occuring during the execution of the planned processes. Currently, the following type is supported:
   • ModifyActivityDuration: Describes that the duration of the activity identified by id is extended by by time units at time at.
5. GoalDefinition: This element contains the formula defining the costs associated with a schedule and defines the direction of optimization: Either min (for minimization) or max (for maximization) can be desired.
   • Sum: All contained elements shall be summed up.
   • Multiply: All contained elements shall be multiplied.
   • FixedValue: A value of fixed size.
   • DynamicValue: A dynamic value identified by a string value. Currently, the following entries are supported:
     • #EARLINESS_ACTIVITY: the total number of earliness time units on all activities.
     • #TARDINESS_ACTIVITY: the total number of tardiness time units on all activities.
     • #EARLINESS_PROCESS: the total number of earliness time units on all processes.
     • #TARDINESS_PROCESS: the total number of tardiness time units on all processes.
     • #MODIFICATIONS: the number of modifications if compared to the baseline schedule.
     • #MAKESPAN: the number of time units between the first start and the latest end of an activity.
     • #CHANGE_PROCESS_END: the number of time units by which the process end times have been postponed (with respect to the baseline schedule).
     • #ACTIVITY_COSTS: the total amount of costs associated with the execution of the activities in the current schedule.

Evaluation Results

The results of the conducted evaluation are provided in CSV format. The cumulated result files contain one single file describing all results in short notation, the detailed result files contain details on every single test run. The column headers can be interpreted as follows:

1. Cumulated CSV
   • File: The name of the file defining the problem instance.
   • P: 0 corresponds to a low, 1 to a high level of process complexity.
   • R: 0 corresponds to a low, 1 to a high level of resource complexity.
   • T: left-shifts are (not) considered if set to 0(1).
   • H: 0 corresponds to a tight, 1 to a wide baseline schedule.
   • Runs: The number of runs performed in the respective setup.
   • Strategy: The applied rescheduling strategy:
     • RescheduleAll corresponds to full rescheduling.
     • MatchupRescheduler2 corresponds to the matchup scheduling strategy.
     • LocalRescheduler1 corresponds to the LRS strategy based on the linear extension scheme.
     • LocalRescheduler2 corresponds to the LRS strategy based on the exponential extension scheme.
     • LocalRescheduler3 corresponds to the LRS strategy based on the logarithmic extension scheme.
     • LocalRescheduler4 corresponds to the LRS strategy based on the exponential extension scheme, taking the best known solution as a starting point in each iteration.
     • LocalRescheduler5 corresponds to the LRS strategy based on the logarithmic extension scheme, taking the best known solution as a starting point in each iteration.
     Note that the results of the latter two methods have only been mentioned in an annotation in the presented paper.
   • Optimizer: The applied optimization heuristics. The genetic algorithm which has been applied for the conducted evaluation has been described in [2].
   • Limit: The stop criterion for optimization.
   • Original: The costs associated with the original baseline schedule.
   • D1 causes: The costs caused by the first disruption, if no intervention is taken.
   • D1 optimized: The average costs remaining after the optimization according to the considered rescheduling strategy.
   • best: The best value found throughout all runs conducted for the respective case.
   • %: The percentage of the thereby defined optimization potential that could be tapped by use of the optimizer on average.
   • found after: The number of milliseconds that had passed on average when the optimal solution was found.
   • found by: Statistics on the optimizer which found the optimal solution.
   • Schedules: The number of schedules analyzed on average.
   • Time Run: The number of milliseconds required for the entire run on average, including all pre- and postprocessing.
2. Detailed CSV
   • Strategy: The applied rescheduling strategy:
     • RescheduleAll corresponds to full rescheduling.
     • MatchupRescheduler2 corresponds to the matchup scheduling strategy.
     • LocalRescheduler1 corresponds to the LRS strategy based on the linear extension scheme.
     • LocalRescheduler2 corresponds to the LRS strategy based on the exponential extension scheme.
     • LocalRescheduler3 corresponds to the LRS strategy based on the logarithmic extension scheme.
     • LocalRescheduler4 corresponds to the LRS strategy based on the exponential extension scheme, taking the best known solution as a starting point in each iteration.
     • LocalRescheduler5 corresponds to the LRS strategy based on the logarithmic extension scheme, taking the best known solution as a starting point in each iteration.
     Note that the results of the latter two methods have only been mentioned in an annotation in the presented paper.
   • Optimizer: The applied optimization heuristics. The genetic algorithm which has been applied for the conducted evaluation has been described in [2].
   • Limit: The stop criterion for optimization.
   • Original Value: The costs associated with the original baseline schedule.
   • D1 causes: The costs caused by the first disruption, if no intervention is taken.
   • D1 optimized: The costs remaining after the optimization according to the considered rescheduling strategy.
   • List: The best identified solution denoted as an (ordered) list of activities, which can be converted into the corresponding schedule by use of the Serial Schedule Generation Scheme [3].
   • Schedules: The number of analyzed schedules.
   • Time Run: The number of milliseconds required for the entire run, including all pre- and postprocessing.

References

[1] J. Kuster, D. Jannach, G. Friedrich, Local Rescheduling - A Novel Approach for Efficient Response to Schedule Disruptions, Technical Report (2006).

[2] J. Kuster, D. Jannach, G. Friedrich, Handling Alternative Activities in Resource-Constrained Project Scheduling Problems, Proceedings on the 2007 Internation Joint Conference on Artificial Intelligence (2007), to appear.

[3] R. Kolisch, S. Hartmann, Heuristic Algorithms for solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis, J. Weglarz (Ed.), Project scheduling: Recent models, algorithms and applications (1999), 147–178.