LA CONSTRUCTION DES HORAIRES JOURNALIERS MODELES PLNE

LA CONSTRUCTION DES HORAIRES JOURNALIERS MODELES PLNE

Le modele explicite Dantzig

Le premier modèle de couverture de charge est dû à Dantzig dès 1954 [Dan54]. La construction des vacations se repose sur des modèles de couverture ensemblistes3 , décrit par les équations (1) et (2). Min = = m j z CjX j 1 (1) = ≥ m j AijX j Bi 1 , I=1,..,n et Xj ≥ 0, entier (2) Où n=nombre d’intervalles à couvrir dans l’horizon de planification, m= nombre de vacations valides Cj = coût lorsqu’un salarié est affecté à la vacation j Aij = 1 si l’intervalle i est couvert par la vacation j, 0 sinon Bi = nombre de salaries requis pour l’intervalle i Xj = nombre de salaries affectés à la vacation j En amont du traitement par le modèle, l’ensemble des vacations valables est énuméré explicitement par rapport à l’ensemble des règles légales et d’usage. Exemple : la durée totale de travail ne doit pas dépasser 10 heures ; une pause ne débute qu’après 2 heures de travail effectif, etc. Le modèle compte le nombre des salariés à chaque vacation, de telle sorte que les besoins par intervalle B sont satisfaits, tout en minimisant le coût total des affectations. Exemple : Avec un seul type de vacation, sur une journée constituée de 9 intervalles d’une heure, les durées de la vacation sont de 4 à 7H L’exemple comprend des vacations de durées de 4H (vacations a(j)), 5H : b(j), 6H : c(j) ou 7H : d(j), soit un total de 30 vacations.Quant aux vacations sans pause sur une durée de 9H, il y a 6 vacations de 4H, 5 de 5H, 4 de 6H, 3 de 7H. Au total, on décompte 6+5+4+3+30 = 48 vacations. Dans la pratique, un très grand nombre de vacations doit être utilisé afin de tenir compte de • la souplesse inhérente à une charge définie au quart d’heure près • des journées de longueurs différentes • différents horaires de début, ou des pauses repas différentes [Kla73] rapporte un nombre avoisinant 15000 vacations sur une journée, [BJ00] mentionne des milliards de horaires possibles sur une semaine. La génération de toutes les vacations pour la résolution avec ce modèle prendrait un certain temps. Chaque vacation étant représentée par une variable, les systèmes d’équations résultants sont trop grands pour être résolus par les logiciels disponibles aujourd’hui. D’où la motivation de la modélisation implicite des vacations.  

Le modélé implicite   Moondra

Moondra fut le premier [Moo76] à proposer un modèle implicite où chaque vacation n’est plus représentée qu’implicitement par le nombre d’agents qui démarrent ou qui terminent au cours d’une intervalle p. Afin de traiter les différences des coûts, on crée des groupes pour les vacations ayant le même coût par période travaillée, la même pause repas et les mêmes restrictions en durée de travail (bornes sur la durée totale de la vacation et la durée travaillée sans interruption).