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,
- Constructive Heuristics
- Improvement 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 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.
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.
If you would like to know more about data-driven actionable insights for your project schedule, then feel free to contact meat firstname.lastname@example.org.