A heuristic framework for Resource-Constrained Project Scheduling Problem (RCPSP).

A Resource-Constrained Project Scheduling Problem (RCPSP) is an optimization problem in project scheduling [1]. It involves scheduling project activities while respecting both resource limits and task dependencies.

• Activities: Tasks with specific durations that require resources.
• Precedence Constraints: Rules dictating the order of tasks.
• Resources: Limited entities (e.g., labor, machinery) required by activities.
• Objective: Typically to minimize project duration (makespan) while adhering to constraints.

• Combinatorial Complexity: Numerous possible schedules as activities and resources increase.
• Interdependencies: Complex relationships between tasks and resources.
• Optimization Trade-offs: Balancing speed, resource efficiency, and other factors.

• Construction: Scheduling labor and equipment.
• Software Development: Coordinating developers, testers, and designers.
• Manufacturing: Allocating machinery and materials. [2]

This framework implements the meta-heuristic Simulated Annealing (SA) to iteratively improve a starting solution. A RCPSP solution is represented by a sequence of activities. By altering the sequence and checking its compliance with the precedence and resource constraints, the solution space is iteratively explored. Simulated Annealing is an optimization technique inspired by the annealing process in metallurgy, where materials are heated and then slowly cooled to reach a stable state. In optimization, it is used to find an approximate global minimum of a function. The algorithm works by exploring the solution space, occasionally accepting worse solutions to escape local minima. As the "temperature" parameter gradually decreases, the algorithm becomes less likely to accept worse solutions, focusing on refining the current best solution until it stabilizes at a near-optimal solution.

The neighborhood types describe how to generate a neighboring solution from an existing solution. We tested the neighborhood types SWAP, SHIFT, adjacent pairwise interchange (API) [1], and RANDOM. In the following example RCPSP instance we will show how the different neighborhood types alter the sequences of activities. The precedence constraint can be visualized by a graph. Each node represents an activity. An edge from node a -> b means that activity a must be finished before b can start. Consider the following precedence graph of a simple RCPSP instance:

The SHIFT neighborhood is defined by two activities between which all activities are shifted back or forth in the sequence and the overflowing element is rolled around.

In this example, the activity 1 and 4 are selected. All activities in between are shifted forward and element 1 is rolled around at the end of the subsequence.

The following example shows a subsequence shift that results in a solution that violates the precedence constraint, according to the precedence tree. Activity 6 needs to be finished before activity 1 can start.

The SWAP neighborhood selects two activities that swap positions in the sequence. The activities in between remain in the same position. In this example activities 1 and 3 are swapped, resulting in a slightly changed but still valid schedule.

Swapping activities 6 and 3 will result in an invalid solution. In this case, two precedence constraints are violated. Activity 6 needs to be finished before activity 1 can start. Activities 3 and 7 analogously.

Solutions generated by API are a subset of the solutions derived in the SWAP neighborhood. This scheme is best described in Brucker and Knust [1].

This scheme creates random sequences that are often infeasible due to the precedence constraints.

The representation of a correct RCPSP schedule in a Gantt chart is also a hard optimization problem. Our implementation uses Depth First Search (DFS) to find a valid representation of the RCSPS schedule.

The scheduler was tested against selected RCSPS instances with best-known solutions. Given a fixed time frame, different neighborhood types for the Simulated Annealing were tested using a number of given random seeds.

The following box plot shows the scheduling results of selected RCPSP instances with respect to the neighborhood type.

The y-axis shows the deviation of our solutions from the best-known solution of each instance. It can be observed that for some instances the best-known solution is found in each run (X10_9, X30_8, X42_7, X55_10). Other instances seem to be more difficult to solve (X6_8, X27_6, X51_6, X58_3, X59_3). For most instances, the swap-neighborhood results in the least deviation from the best-known solution. The larger instances (X58_3, X59_3) show a smaller spread in deviation, compared to the smaller instances. For the larger instances sometimes no solution was found within the fixed time frame.

The instances can be found in ScheduleMe/benchmark_instances.

[1]: Brucker, Peter, et al. "Scheduling models." Complex scheduling (2012): 1-28.

[2]: Schwindt, Christoph, and Norbert Trautmann. "Batch scheduling in process industries: an application of resource-constrained project scheduling." OR-Spektrum 22 (2000): 501-524.