| Abstract |
|---|
| 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, which is based on an iterative Lagrangian heuristic, 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. |
| Contact |
| Dag Wedelin Dept of Computing Science,Chalmers Univ of Tech,SE-41296 Guteborg,SWEDEN, dag@cs.chalmers.se |