Fabrication d'horaires personnalises avec priorites pour les equipages aeriens (French text)

The subject of the thesis relates to the construction of monthly personalized schedules with priorities in air transportation, the PREFERENTIAL BIDDING SYSTEM (PBS). This system is used in several airline companies, since May 1995, in particular at Air Canada, for the construction of the monthly schedules of the pilots and the first officers. The goal of the PBS system is to build sequentially, on a monthly basis and according to the seniority order, an acceptable schedule for each employee of maximum pointing and covering all pairings. The respect of the seniority order seems to facilitate the problem since it imposes a sequential approach of resolution. However, searching the best schedule for each employee is a difficult problem to be solved. Not only do we have to maximize the satisfaction of each employee by completely respecting the seniority order but we also have to ensure that, at each stage, the built schedules are compatible between them and allow us to assign residual pairings to the remaining employees. After having described the types of monthly schedules in air transportation and the difficulties met for building these schedules (chapter 1), we will focus in chapter 2 on how are built monthly personalized schedules. We will explain: characteristics and similarities of the various approaches building these schedules; concept of equity during the building process of these schedules where all the employees must be satisfied equitably; concept of strict priority where the satisfaction of the preferences of a more senior employee has priority on any other employee more junior than him; and also various approaches of resolutions found in the literature for the two processes of building these personalized schedules. We will describe the modeling of the problem of building personalized schedules with priorities as well as a glimpse of the technique of column generation used for the resolution of this problem. This technique is usually used to solve optimization problems of big size and was often applied to industrial applications which can't be solved with other methods. A general description of the thesis is given in chapter 4. We summarize briefly the various contributions which we worked out with the goal of improving the current PBS system, as well as the main conclusions we stated after our experiments. (Abstract shortened by UMI.)...