Project scheduling with time windows. From theory to applications. (Q1890184)

In the book resource-constrained project scheduling problems with temporal constraints (minimal and maximal time-lags, time windows) are considered. After an introduction to the model, important constrained propagation techniques for disjunctive and cumulative scheduling problems are described (especially interval consistency tests). Based on these tests a time-oriented branch-and-bound-algorithm is developed in which possible starting times for the activities are enumerated. The constraint propagation tests are used in order to reduce the starting time domains of the activities and to detect infeasibility of certain subproblems. The presented computational results show that this algorithm is one of the best algorithms for the considered problem developed so far. Afterwards, the described constraint propagation and branch-and-bound techniques are generalized to the multi-mode situation. Finally, two applications from airport operations management are presented for the multi-mode model: scheduling of ground handling operations amd airport gate scheduling. It is shown that extensions of the developed branch-and-bound algorithm provide quite good results for real-world data.