DAISy Dynamic Ambient Intelligent Systems Unit

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 large number of processors. The novel parallel ptimizer approach of the paper also achieves almost inear speedups for large problems solved on a small umber of workstations. The Lufthansa problems that ere used in our experiments validate our theoretical esults and prove the value and usefulness of our work.