Parallel algorithms for airline crew planning on networks of workstations

This work has been supported by the ESPRIT HPCN program. The crew planning problem has been successfully solved on a loosely connected network of workstations (NOW) using advanced computational techniques and efficient communication patterns. The parallelization of the successful sequential system of Carmen Systems AB guarantees that the results are immediately useful and applicable to a large number of airlines scheduling problems. The parallel pairing generator component of the crew scheduling process achieves a linear speedup on the number of processors and can be efficiently scaled to a large number of processors. The novel parallel optimizer approach of the paper also achieves almost linear speedups for large problems solved on a small number of workstations. The Lufthansa problems that were used in our experiments validate our theoretical results and prove the value and usefulness of our work. 1