We describe a tabu search algorithm for a crew scheduling problem which is modeled as an extension of the classical vertex coloring problem. In our model, the tasks to be performed correspond to the vertices of the graph while the employees are the colors to be assigned to the vertices. Our algorithm takes into account the qualifications of the employees as well as minimal and maximal bounds on the workload. Results on preliminary experiments will be given.

We consider the problem of assigning activities and breaks within predetermined shifts in order to satisfy as much as possible the demand for each type of activities as well as a variety of constraints and objectives. We specifically tackle the problem of efficiently optimizing breaks, which are subject to tricky constraints, by modifying an existing heuristic column generation approach embedded in a rolling horizon decomposition strategy. The test set problems are taken among large-scale instances arising from air traffic control.

Nous traitons le problème de construction de quarts de travail avec plusieurs pauses et des contraintes complexes provenant d’applications rencontrées en pratique. Nous proposons un modèle linéaire en nombres entiers avec des contraintes forward et backward. La résolution se fait par une procédure de séparation et d’évaluation progressive qui permet d’atteindre l’optimalité en un temps raisonnable. Notre modèle est aussi comparé à une autre approche de modélisation implicite à travers un jeu de données réelles.