Parallel Crew Scheduling in PAROS

We give an overview of the parallelization work done in PAROS. The specific parallelization objective has been to improve the speed of airline crew scheduling, on a network of workstations. The work is based on the Carmen System, which is used by most European airlines for this task. We give a brief background to the problem. The two most time critical parts of this system are the pairing generator and the optimizer. We present a pairing generator which distributes the enumeration of pairings over the processors. This works efficiently on a large number of loosely coupled workstations. The optimizer can be described as an iterative Lagrangian heuristic, and allows only for rather fine-grained parallelization. On low-latency machines, parallelizing the two innermost loops at once works well. A new “active-set” strategy makes more coarse-grained communication possible and even improves the sequential algorithm.