| Authors: | Alefragis P., Gkoumopoulos C., Housos E., Sanders P., Takkula T., Wedelin D. |
|---|
| Title: | Parallel Crew Scheduling in PAROS |
|---|
| Conference: | 4th International Euro-Par Conference |
|---|
| Editors: | D.J. Pritchard and J. Reeve |
|---|
| Ed: | No |
|---|
| Eds: | No |
|---|
| Pages: | 1104-1113 |
|---|
| To appear: | No |
|---|
| Month: | |
|---|
| Year: | 1998 |
|---|
| Place: | |
|---|
| Pubisher: | Springer |
|---|
| Link: | |
|---|
| File name: | [C6] Parallel Crew Scheduling in PAROS.pdf##^^&&795087519.pdf |
|---|
| 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 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. |
|---|
Greek