3.1 La recherche opérationnelle
Des différentes méthodes ont été
proposées, parmi lesquels nous pouvons citer la programmation
linéaire, la programmation par contrainte ou encore la recherche locale
(méthode Tabou).
D'une manière générale, ces
modèles prennent comme entrée les besoins en personnel et
l'ensemble de règles juridiques. Et comme sortie, ces modèles
repartirent les agents de telle sorte que la somme de leurs
disponibilités couvre au mieux la courbe de charges avec un minimum de
surplus.
Cependant, nous notons que ces approches proposées sont
soit des approches par couverture, soit des approches implicites, soit des
approches explicites.
3.2 Les approches par couverture
Le problème de création de vacations peut
être modélisé comme un problème de recouvrement
d'ensemble. Le premier modèle de couverture de charge dû à
Edie (1954), Dantzig (1954) traitent le cas où l'on aurait un seul type
d'activité, donc une seule courbe de demande à couvrir.
65
La construction des vacations se repose sur des modèles
simplifiés et non-linéaires de couverture ensemblistes qui
cherchent à couvrir une charge en minimisant le nombre de vacations.
Cependant, le modèle Dantzig permet de prendre en compte tout type de
vacation avec un nombre quelconque de pauses. En effet, dans le contexte
aérien, nous préférons de ne pas spécifier de
débuts et fins de pause due aux caractéristiques du travail.
Ainsi afin d'améliorer la solution de Dantzig(1954),
Henderson et Berry ont proposé deux méthodes de résolution
journalière du problème à partir d'un sous-ensemble de
vacations faisables défini à l'aide de plusieurs
paramètres, soit par l'itération de la vacation qui couvre le
plus de tâches non encore couvertes soit par choisir aléatoirement
les vacations du sous-ensemble.
Par la suite afin de choisir les vacations parmi le
sous-ensemble trois méthodes ont été proposés :
- La première méthode est celle utilisée par
Dantzig avec un arrondissement à l'entier supérieur, tout en
essayant de supprimer un agent pour chaque vacation.
- La seconde utilise le résultat de la première et
tente de remplacer deux vacations par une troisième qui fait partie du
sous-ensemble de départ.
- La troisième méthode est identique à la
seconde sauf qu'elle part d'une solution obtenue au hasard.
Les performances de ces méthodes sont, a priori, bonnes
sur des intervalles de temps réduit, mais deviennent plus discutables
lorsque le nombre de quarts augmente.
Segal (1974) inspiré aussi du modèle de Dantzig,
a proposé un algorithme baser sur les modèles de flots. Ce
modèle consiste à modifier dynamiquement la demande en
employés en fonction du temps, sans tenir compte des pauses. Puis, il
fait intervenir une procédure heuristique pour réintégrer
les pauses. Malheureusement, cette méthode de résolution peut
difficilement être étendue au cas multi-activités en
considérant les durées minimales et maximales ainsi que des
coûts de transitions entre les activités distinctes.
66
| 
