Soutenance mémoire
Le transport aérien connaît une croissance vertigineuse depuis les années 60 car, si en 1945, le trafic aérien comptait 9 millions de passagers par an, il est passé aujourd’hui à 1,8 milliard. Les compagnies aériennes sont nombreuses et ont tendance à se grouper car la concurrence est importante. Rester rentable dans un environnement complexe et concurrentiel est d’autant plus difficile qu’une compagnie est obligée de faire face à d’énormes dépenses pour payer le carburant, le personnel, les taxes d’utilisation des aéroports, l’entretien, la location ou l’achat des aéronefs. Les augmentations de recettes étant très difficiles sur ce marché très concurrentiel, une éventuelle réduction des coûts est essentielle pour assurer la rentabilité d’une compagnie.
Planification des ressources humaines
La planification et la gestion optimale des ressources humaines jouent un rôle important dans la productivité et la compétitivité d’une entreprise. Les fonds alloués à la rémunération du personnel sont assez élevés : dans une compagnie aérienne, par exemple, les fonds alloués pour payer le personnel représentent les plus importantes dépenses [Anbil et al. 92] après le coût du carburant ; dans un établissement des soins, les coûts salariaux peuvent représenter jusqu’à 70% du budget opérationnel [Weil et al. 98]. Une gestion efficace du personnel est donc un facteur économique primordial.
Quelques notions sur la planification
La planification d’horaires de travail vise, pour un horizon de planification d’un jour à quelques mois, à dimensionner une force de travail et à optimiser l’utilisation de cette ressource, de façon a couvrir un besoin exprimé par une charge de travail prévisionnelle, tout en respectant un ensemble de contraintes précises. Elle aboutit à des programmes définissant les horaires de travail et de repos de la force de travail, en trouvant le meilleur compromis entre les préférences des différents acteurs [Rémi-Robert, 03].
Les contraintes qui viennent d’être mentionnées couvrent ce que l’on appelle les aspects « JuSTE » [Chan 02] :
Juridique : la législation en matière de droit du travail (durées de travail et de repos) sur différents horizons de temps (journalier, hebdomadaire, mensuel et annuel)
Social : répartition équitable des tâches entre salariés, entre hommes et femmes, avec respect des disponibilités, préférences individuelles et autres souhaits des salariés; répartition équitable du temps de travail et du repos
Technique : les règlements des différents métiers de l’entreprise (prise en compte des compétences et des niveaux requis)
Economique : respect des besoins de l’entreprise à chaque moment de l’horizon de planification. Cela se présente comme la meilleure adaptation de l’énergie disponible aux charges à chaque moment de l’horizon. On cherche à ne pas dépenser inutilement cette énergie.
La difficulté de la création d’un planning est moins le processus de création en lui-même que l’obtention d’un planning de bonne qualité. Comment peut-on définir un planning de bonne qualité, alors qu’au sein d’une entreprise, chacun a son propre point de vue? Le planificateur souhaite que le planning soit assez flexible en ce qui concerne la main d’œuvre, pour pouvoir traiter les possibles imprévus. Pour le chef d’entreprise, le planning doit permettre le dimensionnement de la force de travail au plus juste et sa répartition de manière à obtenir le meilleur service au meilleur coût. Pour l’inspection du travail, le planning doit respecter dans les moindres détails la législation du travail et les conventions collectives. Le salarié recherche la satisfaction sociale de son travail, par rapport à ses disponibilités, à ses desiderata ou par rapport à l’équité de traitement. La création des plannings qui prennent en compte toutes ces contraintes, parfois contradictoires, implique à la fois une bonne connaissance du cadre de travail, mais aussi l’utilisation des techniques d’optimisation combinatoire.
La planification dans un contexte aéronautique
Dans un contexte aéronautique, la charge de travail est constituée des tâches à réaliser en vol et au sol, tâches qui sont déterminées la plupart du temps par le programme des vols. Suivant le type du travail à effectuer, le personnel se divise en deux catégories : le personnel au sol et le personnel navigant.
Personnel au sol
Le programme des vols d’une compagnie aérienne impose un ensemble de tâches à effectuer au sol : l’enregistrement des passagers, l’accueil à l’arrivée et au départ, le service de correspondance et de transit aux aéroports. Ces tâches sont effectuées par ce que l’on appelle le personnel au sol. Le problème de planification du personnel au sol n’est pas directement formulé à partir des tâches à effectuer ; il y a une étape intermédiaire : les tâches doivent être groupées en vacations, et ce sont ces vacations qui sont ensuite affectées au personnel. On appelle « vacation» un ensemble de tâches exécutées consécutivement par la même personne pendant son service journalier. Suivant le type de contrat du personnel, les vacations doivent être créées ou remplies avant d’être affectées aux agents. Généralement, le contrat des agents spécifie des bornes inférieures et supérieures pour la durée du travail journalier et mensuel, l’existence des pauses pendant la journée de travail et leurs durées. Ainsi, chaque type de contrat devient une sorte de « patron » à partir duquel des vacations seront construites et ensuite remplies avec des tâches. Pour plus de clarté, prenons un exemple : soit un agent dont le contrat impose un travail journalier de sept heures au minimum et dix heures au maximum, avec une pause prévue entre 8h00 et 14h00, d’une durée minimum d’une heure et maximum de deux heures. Une vacation qui commence à 6h00 du matin et qui finit à 14h30, avec une pause entre 9h30 et 11h00 respecte les demandes du contrat. Une autre vacation qui commence à 8h00 et finit à 16h00, avec une pause entre 12h15 et 14h00 est aussi une vacation « légale ». Il reste à trouver si les tâches à effectuer ce jour par cet agent peuvent être plus facilement insérées dans la première ou dans la deuxième vacation.
Si, par contre, le personnel travaille en grille, les vacations sont déjà fournies, car chaque case de la grille de travail correspond à une journée de travail, donc à une vacation vide. Les heures de début et de fin étant précisées, il reste seulement à les remplir avec des tâches. Si, par exemple, la grille de travail propre à un certain agent précise que mardi l’agent commence le travail à 7h30 et finit à 15h30, alors la vacation du mardi commence à 7h30 et finit à 15h30 et les tâches que l’agent va effectuer ce jour ne doivent pas dépasser cet intervalle de temps. Dans la littérature, beaucoup de méthodes de résolution du problème de création des vacations reposent sur des approches par recouvrement d’ensemble. Dans une première étape, tout ou une partie de l’ensemble des vacations candidates sont générées ([Easton & Rossin 91], [Bechold & Brusco 94]). Ensuite, les vacations faisant partie de la solution finale sont sélectionnées selon différentes méthodes : à partir d’une première solution générée par la résolution d’un problème de recouvrement d’ensemble relâché ([Dantzig 54], [Morris & Showalter 83]) ou par une heuristique de construction itérative où les vacations sont sélectionnées les unes après les autres ([McGinnis et al. 78], [Brusco & Johns 96]).
[Segal 74] montre que la création des vacations peut être interprétée comme un problème de flot à coût minimal. La méthode de résolution que nous proposons pour la création de vacations part d’une modélisation du problème en tant que problème de bin-packing : les tâches sont assimilées aux objets et les vacations aux conteneurs. Nous avons choisi cette modélisation car, malgré le fait que le problème de bin-packing est NP-difficile, il existe de nombreux algorithmes qui donnent des solutions approchées.
|
Table des matières
Introduction
1. Planification des ressources humaines
1.1 INTRODUCTION
1.2 QUELQUES NOTIONS SUR LA PLANIFICATION
1.3 LA PLANIFICATION DANS UN CONTEXTE AERONAUTIQUE
1.3.1 Personnel au sol
1.3.2 Personnel navigant
1.4 CONCLUSIONS
2. Modèles et techniques de résolution pour les problèmes de planification d’horaires
2.1 INTRODUCTION
2.2 PROBLEMES CLASSIQUES D’OPTIMISATION COMBINATOIRE
2.2.1 Problème d’affectation
2.2.2 Problème de bin-packing
2.2.3 Problème de recouvrement d’ensemble
2.3 TECHNIQUES DE RESOLUTION RETENUES
2.3.1 Méthodes de résolution de problèmes de couplage et d’affectation
2.3.1.1 Bip Match
2.3.1.2 L’algorithme de Busacker et Gowen
2.3.1.3 L’algorithme hongrois
2.3.1.4 Méthode de relaxation Lagrangienne pour le problème d’affectation généralisé
2.3.2 Algorithmes de résolution pour le problème de bin-packing
2.3.2.1 Algorithmes on-line
2.3.2.2 Algorithmes off-line
2.3.3 Génération de colonnes pour la résolution du problème de recouvrement d’ensemble
2.3.3.1 Convergence de la méthode
2.3.3.2 L’algorithme générateur
2.3.3.3 Recherche des solutions entières
2.4 CONCLUSION
3. Création de vacations pour le personnel au sol
3.1 INTRODUCTION
3.2 CONCEPTS DE BASE : TACHES ET VACATIONS
3.2.1 Tâches
3.2.2 Vacations
3.2.3 Personnel
3.3 PRESENTATION DU PROBLEME
3.3.1 Contraintes réglementaires
3.3.2 Méthodes de résolution dans la littérature
3.3.2.1 Modélisation par recouvrement d’ensemble
3.3.2.2 Méthodes itératives
3.4 MODELISATION PROPOSEE
3.4.1 La représentation du temps
3.4.2 Plages horaires
3.4.3 Tâches, vacations, contraintes
3.4.4 Modélisation du problème
3.5 METHODE DE RESOLUTION PROPOSEE
3.5.1 Génération de vacations
3.5.1.1 Construction des patrons de vacations
3.5.1.2 Traitement des tâches fixes
3.5.1.3 Traitement des tâches mobiles
3.5.2 Remplissage de vacations
3.6 RESULTATS OBTENUS
3.7 CONCLUSIONS
4. Création de rotations pour le personnel navigant
4.1 INTRODUCTION
4.2 CONCEPTS DE BASE
4.2.1 Rotations
4.2.2 Activités hors-vol
4.2.3 Personnel
4.3 MODELISATION ET RESOLUTION DU PROBLEME
4.3.1 Contraintes réglementaires
4.3.2 Méthodes de résolution dans la littérature
4.3.3 Modélisation proposée
4.3.3.1 Construction des PdS
4.3.3.2 Construction de rotations à partir des PdS
4.3.4 Résultats
4.3.4.1 Construction des PdS
4.3.4.2 Construction de rotations à partir des PdS
4.3.5 Post traitement des rotations
4.4 PERSPECTIVES : CONSTRUCTION D’ALGORITHMES APPROCHES
4.4.1 Construction de PdS
4.4.2 Constructions de rotations
4.5 CONCLUSIONS
5. Affectation de vacations/ rotations
5.1 INTRODUCTION
5.2 PRESENTATION DU PROBLEME
5.2.1 Contraintes réglementaires
5.3 METHODES DE RESOLUTION DANS LA LITTERATURE
5.3.1 Affectation de vacations
5.3.2 Affectation de rotations
5.4 MODELISATION DU PROBLEME
5.5 METHODE DE RESOLUTION PROPOSEE
5.5.1 Construction de la matrice de coût
5.5.2 Calcul des coûts
5.5.3 L’affectation de réserves pour le personnel navigant
5.5.4 Affectation de séquences
5.6 IMPLEMENTATION ET RESULTATS
5.6.1 Validation de la méthode
5.6.2 Implémentation
5.7 CONCLUSION
Conclusion
Bibliographie
