Solve Resource Constrained Schedules

Solve resource constrained project scheduling problems using constructive and improvement heuristics. 6 min read.

Solving Resource Constrained Scheduling Problems

Project scheduling began as a research track within the mathematical field of Operations Research. The aim was to determine project activity start and finish dates subject to precedence and resource constraints that optimised a particular project objective, i.e. cost, time or resource minimisation.

The problem of finding a schedule of minimal duration by assigning a start date to each activity such that precedence relations, resource availabilities, and other constraints are respected is known as a resource-constrained project scheduling problem (RCPSP).

Initial research conducted in the 1950s focused on network-based techniques, i.e. Critical Path Method (CPM) and Program Evaluation & Review Technique (PERT). However, these techniques ignored resource usage, and it’s the presence of resources which complicates the scheduling process.

Subsequently, mathematical programming approaches were applied, which solves the allocation of limited resources among competing activities in an optimal way. However, this approach is only feasible for small problems due to the computational effort and time involved.

In contrast, approaches based on ‘rule-of-thumb‘ heuristics are capable of finding good and ‘near to optimal’ solutions to RCPSP problem instances of practical size. Over time, two heuristic categories have resulted,

  1. Constructive Heuristics
  2. Improvement Heuristics

Constructive Heuristics

Constructive heuristics start from an empty schedule and add activities one at a time until a feasible schedule is obtained. A prioritisation rule is applied to the project scheduling information to construct a ranked project activity listing. This listing prioritises which activities are assigned to the schedule, and activity start and end dates are determined using a schedule generation scheme.

Improvement Heuristics

Improvement heuristics start from a feasible schedule built using a constructive heuristic. Schedule operations are iteratively performed until a better solution is identified, which is repeated until an optimal local solution is found. Steepest, fastest, and iterated descent are used to find local optimal solutions. To avoid cycling, these solutions are combined with several machine-learning metaheuristics such as Genetic Algorithms (GA), Simulated Annealing (SA), Tabu Search (TS), Swarm Intelligence (SI) etc to create an artificial intelligent solution that outperforms constructive heuristic solutions.

Heuristics Demonstration

Heuristics Summary

Organisations require schedules that are good and fast, which can only be achieved by applying good heuristic procedures. Unlike commercial schedulers that apply simple dispatch rules, sophisticated schedulers like Oritames apply current Operations Research to solve complex project scheduling problems.

Learn More

If you would like to know more about data-driven actionable insights for your project schedule, then feel free to contact meat

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.