Details

Autor(en) / Beteiligte

• Alefragis, Panayiotis
• Goumopoulos, Christos
• Housos, Efthymios
• Sanders, Peter
• Takkula, Tuomo
• Wedelin, Dag
• Pritchard, David
• Reeve, Jeff

Titel

Parallel crew scheduling in PAROS

Ist Teil von

• Euro-Par’98 Parallel Processing, 1998, p.1104-1113

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

1998

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.