Scheduling Problems and the Set Partitioning Model
Scheduling and rostering problems involving valuable resources such as vehicles, machines or personnel occur in many organizations. Efficient utilization of these resources is obviously an important management consideration. The Set Partitioning model provides a natural representation for many scheduling and rostering problems. From a mathematical point of view, these applications give rise to many challenging problems in combinatorial and computational optimization. In this talk, we will outline some practical airline applications of the set partitioning model and then discuss various mathematical properties of the model which explain why some set partitioning problems are relatively easy to solve and others are particularly difficult to solve. We will also outline some computational techniques based on these mathematical properties, which have been developed specifically to provide solutions to practical scheduling problems. Finally we will describe the planning and rostering systems based on set partitioning models which are used by Air New Zealand.