Introduction
Project scheduling is a fundamental challenge in operations research and artificial intelligence. While standard models focus on simple precedence, real-world projects often involve complex temporal constraints, such as maximum time lags between tasks. This paper, originally presented at AAAI 2004, introduces a robust heuristic algorithm designed to solve the Resource-Constrained Project Scheduling Problem with Time Windows (RCPSP/max). By integrating iterative priority learning with a novel conflict-resolution technique called "bulldozing," the authors provide a scalable solution for projects where traditional exact methods often fail to find even a single feasible schedule.
The Challenge of RCPSP/max
In a typical scheduling problem, the goal is to minimize the total project duration (makespan) given limited resources and task dependencies. The RCPSP/max variant introduces arbitrary temporal constraints, which specify minimum and maximum time lags between the start or end of different activities.
These constraints make the problem significantly harder because finding a feasible schedule—one that satisfies all rules—is itself an NP-hard problem. Most greedy algorithms fail in this context because they make local decisions that eventually lead to a state where no future task can be placed without violating a maximum time lag. This "dead-end" nature of the search space requires more sophisticated navigation than simple priority-based scheduling.
Methodology: SWO and Bulldozing
The authors' approach rests on two primary pillars: Squeaky Wheel Optimization (SWO) and a new mechanism termed "bulldozing."
Squeaky Wheel Optimization (SWO)
SWO is an iterative meta-heuristic that treats the scheduling process as a learning loop. It uses a greedy constructor to build a schedule based on a priority list. If an activity is difficult to schedule or causes conflicts, it is identified as a "squeaky wheel." In the subsequent iteration, these troublesome activities are moved higher in the priority list. This allows the algorithm to focus its search on the most constrained parts of the project.
As illustrated above, the specific priority order of activities $A_1, A_2,$ and $A_3$ determines whether a feasible schedule can be found. SWO automates the search for an order (like the third scenario) that satisfies all constraints.
The Bulldozing Technique
While SWO manages priorities, "bulldozing" provides the greedy constructor with the power to resolve local conflicts. In standard algorithms, if a task cannot fit into its allowed time window, the process fails. Bulldozing allows the algorithm to be more aggressive: if task $A_i$ is blocked, the algorithm "bulldozes" the blocking tasks further into the future to create space.
This recursive process ensures that the newly inserted task is accommodated while attempting to maintain the feasibility of the displaced tasks. To counteract the schedule expansion caused by pushing tasks later, the authors also implemented "refilling" techniques (Left Bulldozing and Left Shifting) to tighten the schedule once feasibility is achieved.
Results and Performance
The algorithm, designated SWO(BR), was evaluated against standard benchmarks ranging from 10 to 500 activities. The results demonstrated exceptional reliability and scalability:
- Reliability: SWO(BR) found feasible solutions for all 1,733 benchmark problems, a feat many competing algorithms could not match.
- Optimality: On small-scale problems (J10), the algorithm stayed within 0.2% of the optimal makespan.
- Scalability: On the largest datasets (500 activities), the heuristic outperformed exact branch-and-bound methods, which often timed out before finding a feasible solution. SWO(BR) typically found high-quality schedules in just a few seconds of CPU time while maintaining a small memory footprint (under 15 MB).
Conclusion
The combination of Squeaky Wheel Optimization and bulldozing represents a significant advancement in solving RCPSP/max. By prioritizing feasibility and using localized iterative repair, the algorithm effectively "untangles" complex temporal and resource constraints. Future work may involve integrating more structured meta-heuristics like Tabu Search or incorporating resource constraint propagation to further prune the search space and improve makespan optimization in even larger, more pathological instances.
Summary updated