Bidirectional planning: Improving priority rule-based heuristics for scheduling resource-constrained projects

As projects grow in complexity and size finding realizable schedules which efficiently exploit scarce resources is a challenging task within project management. In this context, the well-known resource-constrained project scheduling problem has extensively been studied during the last decades. Considering restricted per-period availabilities of multiple resource types, a project has to be finished as early as possible by performing a set of jobs related by precedence constraints. In particular, for real-world problems with a large number of jobs, heuristics such as priority rule-based procedures as well as approaches based on meta heuristics are among the methods of choice. Traditionally, such heuristics construct a schedule by planning in a forward direction starting from the project's beginning. In this paper, we introduce backward and bidirectional planning strategies. In order to validate their effectiveness these strategies are incorporated into priority rule-based procedures. A comprehensive numerical investigation shows that the performance of such heuristics is considerably increased in particular when using the bidirectional planning. This indicates that such strategies should also be applied within meta heuristic-based procedures.