The goal in project scheduling is to assign start times to activities so that all constraints are satisfied and some objective function is optimized. A wide range of real-world scheduling applications is matched by a variety of theoretical and experimental results in Artificial Intelligence and Operations Research.
In this dissertation, we suggest a window-based approach to project scheduling. Underlying this approach is the use of a generalized simple temporal problem (GSTP) framework that allows us to maintain for each activity an interval of temporally feasible start times, called a time window. We describe how windows can be maintained during both schedule construction and local search and discuss the properties of time windows for problems with both cyclic and acyclic constraint graphs.
We show that window-based search is effective for two very different problem domains. The first is the resource constrained project scheduling problem with arbitrary temporal constraints (RCPSP /ma:x). We present a new heuristic algorithm that combines the benefits of squeaky wheel optimization with an effective conflict resolution mechanism, called bulldozing, to address RCPSP/max. problems. On a range of benchmark problems, the algorithm is competitive with state-of-the-art systematic and non-systematic methods and scales well.
The second problem for which we use window-based search is the labor cost optimization problem (LCOP) where the objective is to minimize the total labor costs (including wages, overtime, undertime, hire and fire costs). For the LCOP, simply computing the objective function is time-consuming; we show how this computation can be done quickly enough to be incorporated into search. We then describe the ARGOS optimization tool, a collection of algorithms for the LCOP, and show how it can produce significant cost savings over other available approaches on a number of real-world problems. Finally, we describe Sim Yard, a simulation tool for a shipyard environment, and use it to show that the theoretical cost savings of ARGOS schedules should be matched by actual savings in a real-world setting.