Share Cahiers du GERAD par Michel Gamache, François Soumis, Daniel Villeneuve, Jacques Desrosiers et Éric Gélinas Cet article décrit le problème de construction d’horaires mensuels personnalisés avec choix de préférences pour les membres d’équipage (pilotes et officiers) en transport aérien. Ce problème consiste à affecter aux membres d’équipage des rotations, des repos, des vacances, des entraînements, etc., tout en considérant un ensemble de requêtes pondérées réflétant les préférences de chacun. L’affectation doit tenir compte de l’ancienneté de chaque employé: la construction de l’horaire à pointage maximal pour un employé ne doit jamais s’effectuer au détriment de l’horraire d’un employé ayant plus ancienneté. De ce projet de recherche et de développement est né un système informatisé de construction d’horaires personnalisés qui est en usage chez Air Canada depuis le mois de mai 1995. La méthode de résolution employé peut se résumer comme suit. Pour chaque employé, du plus ancien au plus récent selon l’ordre d’ancienneté, un problème résiduel est résolu: étant donné un employé et un ensemble de rotations non affectées, la solution d’un problème linéaire en nombres entiers détermine l’horaire à pointage maximal de l’employé tout en considérant les employés résiduels. La résolution du problème résiduel s’effectue par une méthode d’évaluation et de séparation dans un arbre de branchement où, à chaque noeud de branchement, un problème linéaire est résolu par la technique de génération de colonnes. Les solutions entières sont obtenues en utilisant des plans coupants sans lesquels il n’aurait pas été possible de résoudre certains des problèmes résiduels.