Approaches to Resource-
Constrained Project Rescheduling

This page provides details on the conducted evaluation of GAOR [1] and GMUP [1], as generalized versions of Affected Operations Rescheduling [2] and Matchup Scheduling [3], respectively: The considered problem instances as well as the computational results can be downloaded.

Problem Instances

As regards the testset used for our performance evaluation, the ZIP file provided above contains 800 XML files, describing 100 problem instances for each of the 8 regarded problem classes. The file name contains two numeric segments: The first one describes the class the respective instance is of 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 and the last digit stands for a tight(0) or wide(1) baseline schedule. The second numeric segment in the file name is the case's ID. As regards the structure and 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 and resource requirements.
     • Activity: Describes an activity identified by an id and a descriptive name name. The duration describes how long execution lasts by default.
     • 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.
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 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.

Evaluation Results

The results of the conducted evaluation are provided in CSV format. The former of the above ZIP files contains one single file describing all results in a cumulated notation, the latter one contains details on every single test run. The column headers can be interpreted as follows:

1. Cumulated CSV
   • File: 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: 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, RescheduleAffected to GAOR and RescheduleMatchupPoint to GMUP rescheduling.
   • Optimizer: The applied optimization heuristics.
   • Limit: The stop criterion for optimization.
   • Original: The costs associated with the original baseline schedule.
   • D1 causes: The costs caused by 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 considered strategy on average.
   • found after: The number of milliseconds that had passed on average when the optimal solution was found.
   • found by: The optimizer which found the optimal solution.
   • Schedules: The number of schedules analyzed on average: Note that for GMUP only the number of schedules checked in the last iteration is considered.
   • Time Run: The number of milliseconds required for the entire run on average, including pre- and postprocessing.
2. Detailed CSV
   • Strategy: The applied rescheduling strategy: RescheduleAll corresponds to full, RescheduleAffected to GAOR and RescheduleMatchupPoint to GMUP rescheduling.
   • Optimizer: The applied optimization heuristics.
   • Limit: The stop criterion for optimization.
   • Original Value: The costs associated with the original baseline schedule.
   • D1 causes: The costs caused by 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 (ordered) activity list.
   • Schedules: The number of schedules analyzed: Note that for GMUP only the number of schedules checked in the last iteration is considered.
   • Time Run: The number of ms required for the entire run, including pre- and postprocessing.

References

[1] J. Kuster, D. Jannach, Approaches to Efficient Resource-Constrained Project Rescheduling, Proceedings of the Third Starting AI Researchers Symposium (2006), 208-219.

[2] R.K. Li, Y.T. Shyu and A. Sadashiv, A heuristic rescheduling algorithm for computer-based production scheduling systems, International Journal of Production Research 31 (1993), 1815-1826.

[3] J.C. Bean, J.R. Birge, J. Mittenthal and C.E. Noon, Matchup Scheduling with Multiple Resources, Release Dates and Disruptions, Operations Research 39 (1991), 470-483.