| Article ID: | iaor20083267 |
| Country: | United Kingdom |
| Volume: | 34 |
| Issue: | 8 |
| Start Page Number: | 2384 |
| End Page Number: | 2395 |
| Publication Date: | Aug 2007 |
| Journal: | Computers and Operations Research |
| Authors: | Hertz Alain, Gamache Michel, Ouellet Jrme Olivier |
| Keywords: | scheduling, graphs, heuristics: tabu search, programming: branch and bound |
We consider a monthly crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a tabu search algorithm for determining if the problem contains at least one feasible solution. We then show how to combine the proposed approach with a heuristic sequential scheduling method that uses column generation and branch-and-bound techniques.