Télécharger le fichier pdf d’un mémoire de fin d’études

1.3 Typologie des courses

Un programme de courses est la liste de toutes les courses planifi´ees sur un intervalle de temps donn´e (g´en´eralement trois mois). Les courses se d´eroulant le mˆeme jour et sur le mˆeme hippodrome sont regroup´ees dans ce qu’on appelle une r´eunion. G´en´eralement, chaque r´eunion peut comprendre jusqu’`a neuf courses. Les courses sont class´ees en diff´erents types de course, suivant l’ˆage des chevaux, la distance et la cat´egorie de la course. Ainsi, dans cette section, nous d´etaillons les diff´erentes carac-t´eristiques qui d´efinissent le type d’une course. Dans la section suivante, on pr´esentera l’allure typique de la carri`ere d’un cheval, pour mieux comprendre les interactions entre les diff´erents types de courses.

1.3.1 Conditions d’ˆage

Pour pouvoir participer a` une course donn´ee, un cheval doit en premier lieu r´epondre a` un crit`ere d’ˆage 3. Il existe trois classifications principales : les courses pour chevaux de deux ans, celles pour chevaux de trois ans, et les courses pour chevaux de quatre ans et plus. Des courses sp´ecifiques pour les chevaux de quatre ans ou plus de cinq ans sont ´egalement organis´ees. On peut observer tr`es occasionnellement d’autres conditions, comme des courses d´edi´ees aux chevaux de trois ans et plus.

3. L’ˆage d’un cheval change au premier janvier. Un cheval n´e le 12 aoˆut 2015 sera consid´er´ comme un cheval de trois ans d`es le 1er janvier 2018.

1.3.2 Distances

Il existe plusieurs plages de distances sur lesquelles se d´eroulent les courses (Fig. 1.2). Les courses les plus courues sont les courses Flyer, entre 800 et 1400 m`etres. Il y a ensuite les courses Miler de 1450 a` 1800 m`etres, les courses Intermediate de 1850 m`etres a` 2150 m`etres, les courses Classical de 2200 a` 2400 m`etres et, pour finir, les courses Stayer pour les distances sup´erieures (de 2450 m`etres a` 3200 m`etres).

1.3.3 Cat´egories

Les cat´egories de courses sont r´eparties en trois groupes, qui se distinguent par les conditions d’inscription, et les r`egles de la course.
Courses `a Handicap
Dans une course a` Handicap, les chevaux partants portent des poids pour courir. Th´eoriquement, les poids sont choisis de sorte que tous les chevaux aient une probabilit´e ´egale de l’emporter, qu’ils soient ainsi sur un pied d’´egalit´. Le poids que devra porter chaque cheval est d´ecid´ par le handicapeur, dont c’est le m´etier, sur la base des performances r´ecentes du cheval. Le poids a` porter est appel´ valeur du cheval, et varie typiquement entre 15 kilogrammes, pour les chevaux les moins performants, a` 50 kilogrammes pour les chevaux les plus performants (les cracks). Evidemment, le poids du jockey est pris en compte lors du calcul du poids suppl´ementaire (chaque jockey se soumet `a une pes´ee avant la course). Par nature, ces courses sont destin´ees `a une population de chevaux assez large puisque un entraˆıneur peut esp´erer gagner mˆeme avec un cheval moins fort que ses concurrents. Ce sont donc des courses qui ont en g´en´eral beaucoup de partants. Toutefois, les courses `a Handicap ne sont pas toujours ouvertes `a tous ; il peut y avoir des conditions d’inscription suppl´ementaires sur la valeur des chevaux partants. R´eguli`erement, une course `a Handicap est ainsi support d’´ev´enement. La r´ecompense accord´ee au premier est alors bien plus importante que dans un Handicap de mˆeme niveau non support d’´ev´enement. On attend alors beaucoup de partants et des paris complexes (comme le quint´e) sont organis´es.
Courses `a R´eclamer
La deuxi`eme cat´egorie de course sont les courses `a R´eclamer. A la fin de la course `a r´eclamer, les partants sont vendus aux ench`eres. Comme dans la course `a Handicap, chaque cheval porte un poids. En revanche, le poids ne d´epend pas directement de la valeur du cheval, mais d´etermine le prix initial de la mise aux ench`eres du cheval (plus le poids est important, plus la mise `a prix est elev´ee). Un poids minimum est impos´e dans les conditions de participation, mais chaque propri´etaire peut d´ecider de faire porter un poids plus important `a son cheval, pour le vendre plus cher.
Courses `a Conditions
Une course a` Condition, comme son nom l’indique, est une course pour laquelle la participation est soumise a` une (ou des) condition(s). Certaines peuvent, par exemple, d´ependre de la valeur du cheval et de ses gains cumul´es.
Parmi les courses a` Condition, on trouve plusieurs cat´egories de courses. Tout d’abord, il y a les courses d’In´edits et les courses Maiden, r´eserv´ees aux chevaux d´ebutants, pour les accompagner et faciliter leur insertion dans le circuit comp´etitif. Les courses d’In´edits sont r´eserv´ees aux chevaux n’ayant jamais couru, les courses Maiden sont r´eserv´ees aux chevaux n’ayant jamais gagn´e.
Ensuite, on trouve les courses a` Condition qui constituent le circuit comp´etitif du programme. La participation est soumise a` des conditions portant sur la valeur du cheval et sur son palmar`es. Les plus accessibles sont les courses a` Condition C4, suivies des C3, des C2, et des C1. On trouve ensuite les courses Listed, et les courses de Groupe, r´eserv´ees a` l’´elite. Comme les courses a` Condition, et en particulier celle de niveau tr`es elev´e, sont plus s´electives, on y attend moins de partants que dans les courses a` r´eclamer ou a` Handicap.
N.B. : Il existe encore bien d’autres conditions de participation, li´ees par exemple a` la race du cheval (les courses AQPS pour les chevaux autres que les pur sang) qui n’ont pas et´ pr´esent´ees en d´etail. A titre informatif, nous pouvons citer ´egalement des conditions associ´ees aux jockeys comme les courses r´eserv´ees aux femmes jockeys, et les courses r´eserv´ees aux jockeys amateurs. Elles sont plutˆot d’ordre exceptionnel, et ne changent pas la compr´ehension du probl`eme. Nous ne les prendrons pas en compte dans cette ´etude.

1.4 Contraintes du probl`eme

Dans cette section, nous donnons les contraintes du probl`eme telles qu’´enonc´ees par France Galop. Nous avons d’une part des contraintes dures, mat´erielles ou ´emanant du code des courses, et d’autre part des contraintes souples. Ces contraintes souples correspondent a` des heuristiques de planification utilis´ees par les experts pour produire des programmes de qualit´e. Avant de les pr´esenter, nous don-nons quelques d´etails concernant la carri`ere typique d’un cheval pour apporter une explication aux contraintes.
Une partie importante de la th`ese porte sur la formalisation de ces contraintes, notamment dans la sections 4.5 o`u l’on proposera un mod`ele math´ematique lin´eaire, et en section 5.2 ou l’on d´etaillera l’expression de la fonction objectif utilis´ee dans les m´ethodes de r´esolution approch´ees.

1.4.1 Carri`ere d’un cheval

Un des objectifs de la planification est d’attirer le plus de partants possible aux diff´erentes courses. Pour ce faire, il est important de comprendre comment les entraˆıneurs et propri´etaires utilisent le programme pour composer la carri`ere de leurs chevaux. Dans cette section, sont discut´ees les carri`eres type des chevaux pour comprendre l’interaction entre les diff´erentes courses, et donner du sens aux contraintes du probl`eme.
Un cheval peut commencer a` courir a` partir de ses deux ans, a` partir du 25 mars. Puisque les courses d’In´edits sont r´eserv´ees aux chevaux n’ayant jamais couru, un cheval d´ebute normalement sa carri`ere par une course d’In´edits. Un cheval qui gagne une course d’In´edits va g´en´eralement se diriger vers une course C2, pour entrer dans le circuit comp´etitif. Si, en revanche, il ne gagne pas, il va participer a` une course Maiden, r´eserv´ee aux chevaux n’ayant jamais gagn´e. La majorit´e des courses d’In´edits et des courses Maiden sont donc logiquement r´eserv´ees aux chevaux de 2 ans, mais on en trouve aussi pour les chevaux de 3ans. Il y a des chevaux qui commencent leur carri`ere tardivement, mais aussi qui se reconvertissent en coureur de plat, apr`es avoir couru des courses d’obstacles. On observe ensuite deux profils types. Certains chevaux vont avoir un niveau suffisant pour participer aux courses a` Condition. S’ils y sont performants, ils pourront pr´etendre a` des courses de plus en plu s´electives. D’autres chevaux vont plutˆot participer aux courses a` Handicap et a` celles a` R´eclamer.
La figure 1.3 illustre la progression typique d’un cheval de deux ans. A l’issue d’une course, les chevaux plac´es, c’est-a`-dire finissant parmi les 5 premiers, vont souvent chercher a` participer a` une course de meilleur niveau. Par exemple un cheval plac´e a` une course C2 pourra vouloir courir une course C1 ensuite. Toutefois, la figure 1.3 est purement indicative et d’autres transitions ont bien sˆur lieu.
En ce qui concerne les distances courues, les chevaux jeunes vont chercher leur distance de confort, d’autant plus que les distances importantes ne sont accessibles aux chevaux de 2 ans que tard dans l’ann´ee. Ensuite, les entraˆıneurs inscriront leurs chevaux, en priorit´e, a` des courses sur leur distance de pr´edilection.

1.4.2 Contraintes dures de la planification

1.4.2.1 Code des courses au galop

Le code des courses au galop [1] r´eglemente tout ce qui a trait aux courses de galop, de la naissance des chevaux, au versement des gains. On y trouve par exemple le d´etail du processus d’inscription d’un cheval a` une course, des v´erifications a` effectuer avant une course, ou encore de l’achat des chevaux mis a` r´eclamer. En revanche, il ne contient quasiment aucune r`egle concernant directement la r´ealisation d’un programme de courses. Nous prendrons seulement note de la r`egle suivante, portant sur les distances que peut courir un cheval en fonction de son ageˆ :
— La distance d’une course ne peut ˆetre inf´erieure a` 1000 m`etres dans les Handicaps ou a` 800 m`etres dans les autres courses.
— Les courses ouvertes aux chevaux de deux ans sont soumises aux restrictions suivantes :
a) du jour de l’ouverture des courses plates jusqu’au 30 avril inclus, lesdites courses doivent ˆetre r´eserv´ees aux chevaux de deux ans et d’une distance au plus ´egale a` 1000 m`etres. Toutefois, des d´erogations a` ces dispositions peuvent ˆetre accord´ees par les Commissaires de France Galop.
b) du 1er mai au 31 aoˆut, lesdites courses ne peuvent ˆetre que des prix r´eserv´es aux chevaux de deux ans, d’une distance au plus ´egale a` : 1200 m en mai, 1400 m en juin, 1600 m en juillet. Toutefois, des d´erogations aux dispositions des alin´eas a) et b) peuvent ˆetre accord´ees par les Commissaires de France Galop.
c) a` partir du 1er octobre, les dites courses peuvent ˆetre des Handicaps a` condition d’ˆetre r´eserv´ees aux chevaux de deux ans.
d) a` aucun moment les courses ouvertes aux chevaux de deux ans ne peuvent ˆetre disput´ees sur une distance sup´erieure a` 2000 m`etres.

1.4.3 Autres contraintes dures

Des contraintes dures suppl´ementaires s’appliquent.
— Les courses pour les chevaux de 2 ans ne commencent pas avant le 25 mars.
— Pour les chevaux de 3 ans les courses sur les distances de 2400 m et plus ne peuvent pas commencer avant le 15 avril. Celles sur une distance de 3000 m et plus, ne peuvent d´ebuter avant le 10 juin.
— Tout d’abord, le nombre de courses que peut accueillir une r´eunion est limit´e par la dur´ee d’une journ´ee de courses. La d´ecision du nombre de courses dans une r´eunion ne nous revient pas, mais le respect de cette d´ecision est une contrainte dure.
— Pour chaque hippodrome, seules certaines distances peuvent ˆetre organis´ees, en fonction de la piste, en particulier les courses Flyer devant ˆetre courues sur une ligne droite. En effet, un
hippodrome ne peut pas accueillir de courses Flyer s’il ne dispose pas d’une ligne droite d’entre` 1000 m et 1400 m. A titre d’exemple, du fait de la r`egle sur les distances ´emanant du code des courses, il est possible qu’un hippodrome puisse organiser une course Maiden de distance Flyer
29 pour des chevaux de 2 ans en automne, en juin, mais pas en mars.

1.4.4 Contraintes souples

A ces contraintes dures s’ajoutent des contraintes souples. Ces contraintes nous on et´ donn´ees par les experts, dans un travail de formalisation du processus manuel de planification. Il s’agit donc d’habitudes de planification, bas´ees sur leur exp´erience.

1.4.4.1 Contrainte d’´ecart

Entre chaque participation, un cheval a besoin d’un temps de repos. La planification prend en compte ce temps de repos pour faire en sorte qu’un cheval qui ne soit pas au repos ait toujours une course a` laquelle il puisse s’inscrire et ainsi progresser dans sa carri`ere. En pratique, cela se traduit par la r`egle suivante : pour toute course planifi´ee, on planifiera toujours une course de mˆeme distance (Flyer, Miler, Intermediate, Classical, ou Stayer), de mˆeme catg´eorie (Handicap, R´eclamer, …) et pour le mˆeme ageˆ (2 ans, 3 ans, ou 4 ans et plus) dans un intervalle de temps d´etermin´ apr`es la premi`ere course (par exemple, entre 18 et 25 jours plus tard), qui d´epend de la distance. Ainsi, tout cheval courant une course aura la possibilit´e de courir une course similaire apr`es sa p´eriode de repos. On demande aussi qu’un tel ´ecart soit respect´ entre une course a` In´edits et une course Maiden, pour que les chevaux courant une course a` In´edits aient la possibilit´e de courir une course Maiden apr`es leur p´eriode de repos.

1.4.4.2 Contrainte HR

On veut que chaque r´eunion soit compos´ee d’un m´elange de course comp´etitives et de courses plus accessibles. Ainsi, chaque r´eunion doit contenir de 3 a` 5 courses a` Handicap ou a` R´eclamer (en privil´egiant les courses a` Handicap), dans la mesure du possible, compte tenu de la capacit´e de la r´eunion.

1.4.4.3 Contrainte de Paires

Certains types de courses doivent ˆetre planifi´es par paire, c’est-a`-dire que le mˆeme type de course doit ˆetre planifi´e deux fois dans toute r´eunion o`u il est planifi´e. C’est le cas des courses a` Handicap pour les chevaux de 4 ans et plus, car elles accueillent beaucoup de partants. C’est ´egalement le cas pour les courses Maiden, pour lesquelles on planifiera une course pour les mˆales et une pour les femelles.

2.2 Planification d’´ev`enements sportifs
Comme indiqu´e en introduction, il n’existe pas a` notre connaissance d’´etude portant sur la plani-fication des courses de chevaux. Il est int´eressant de noter par ailleurs que la planification des courses
´
de chevaux peut ˆetre tr`es diff´erente suivant les pays. Aux Etats-Unis, la probl´ematique g´eographique est tr`es important du fait de la taille du pays. Au Royaume-Uni, les paris passent par des bookmakers, ce qui impacte bien sˆur la strat´egie de planification.
On peut tout de mˆeme, th´ematiquement, rapprocher le probl`eme etudi´ des probl`emes de planifica-tion d’´ev`enements sportifs. Ce type de probl`eme est relativement r´epandu en Recherche Op´erationelle, comme en t´emoigne la revue de litt´erature portant sur ce th`eme par Kendall et al. [2].
La planification des rencontres de football et de baseball en particulier ont de nombreuses appli-cations. La planification des rencontres de la IFL (Italian Football League) a par exemple et´ etudi´ee par Della Croce et al. [3]. Une des contraintes r´ecurrentes dans ce type de probl`eme est l’assurance d’une bonne alternance entre les rencontres a` domicile et les rencontres a` l’ext´erieur pour les ´equipes. Dans cet article, l’affectation des droits de diffusions des rencontres aux diff´erentes chaˆınes de t´el´-vision fait ´egalement partie de la planification. Les auteurs proposent alors une m´ethode heuristique bas´ee sur la r´esolution successive de plusieurs programmes lin´eaires en variables enti`eres (PLNE). Un
34
2.3. GESTION DE L’INCERTITUDE
premier PLNE d´etermine des motifs possibles pour l’alternance rencontre a` domicile/`a l’ext´erieur. Un deuxi`eme PLNE constitue un calendrier en combinant ces motifs. Un dernier PLNE affecte les ´equipes aux motifs.
Un exemple dans un autre sport, l’´etude de Taeho Kim [4] sur la ligue de baseball sud-cor´eenne (sport le plus regard´ en Cor´ee du Sud). Ici, on cherche a` minimiser la distance parcourue pour les ´equipes. L’alternance entre rencontres a` l’ext´erieur et a` domicile est toujours soumise a` des contraintes, et on trouve ´egalement les contraintes relatives au format du tournoi. Le probl`eme est mod´elis´ par un programme lin´eaire a` variables mixte-enti`eres, et une heuristique est ici aussi propos´ee.
Le probl`eme de planification des courses de galop a finalement assez peu de points en commun avec les autres probl`emes de planification sportive sur le plan th´eorique. Une diff´erence majeure est la pr´esence d’incertitude. Il ne semble pas que la robustesse et le traitement de l’incertitude soient des probl´ematiques qui apparaissent habituellement dans les probl`emes de planification sportive. Dans notre probl`eme, on ne sait pas quels chevaux participeront aux courses organis´ees, puisque chaque entraˆıneur d´ecide librement des courses auxquelles il inscrit ses chevaux. On a donc naturellement des probl´ematiques tr`es diff´erentes des probl`emes traditionnels de planification sportive, o`u le but est g´en´eralement de g´erer l’enchaˆınement pr´ecis des rencontres. On veut proposer a` chaque entraˆıneur une offre de courses qui soit satisfaisante quels que soient ses objectifs et le profil de ses chevaux. Cette vision de la planification est donc bien oppos´ee a` l’objectif typique d’imposer a` des ´equipes un calendrier. Par ailleurs, on planifie plusieurs centaines de courses par trimestre, pour plusieurs milliers de coureurs, alors qu’une ligue professionnelle compte typiquement quelques dizaines d’´equipes tout au plus. Enfin, mˆeme si nous planifions avec un horizon de planification fix´e, il faut assurer que les diff´erents programmes trimestriels s’enchaˆınent avec souplesse, par opposition a` la planification d’un tournoi prenant place sur une plage de temps fix´ee, et avec un nombre de rencontres fix´e.
2.3 Gestion de l’incertitude
La gestion de l’incertitude portant sur la participation est l’un des deux axes principaux de la
´
th`ese, avec la production de programmes respectant les contraintes dures et souples. Etant donn´e un programme de courses, le nombre de partants que va g´en´erer le programme n’est pas connu `a l’avance. La source d’incertitude est double : d’une part, les nombres de partants aux courses d´ependent de
35
2.3. GESTION DE L’INCERTITUDE
facteurs ext´erieurs a` la planification, et peuvent donc, pour un programme donn´e, ˆetre consid´er´es pour chacune des courses comme des variables al´eatoires (qui ne sont a priori pas ind´ependantes) ; d’autre part, les lois que suivent ces variables al´eatoires sont inconnues. Par ailleurs, l’incertitude se situe uniquement dans la fonction objectif, et non dans les contraintes du probl`eme a` l’inverse, par exemple, des probl`emes de la litt´erature pour lesquels l’incertitude ´emane souvent d’une demande incertaine.
La prise en compte d’une incertitude portant sur la fonction objectif apparaˆıt notamment dans le probl`eme de s´election de routes, un sous-probl`eme du probl`eme de gestion des flux du trafic a´erien. Le but du probl`eme est de s´electionner parmi un ´eventail de routages pour les avions, celui qui engendrera le moins de coˆuts dus a` des retards au d´epart et a` l’arriv´ee (li´es a` la surconsommation de carburant). Le probl`eme est etudi´e entre autres par Tian et al. [5] pour l’espace a´erien CSC (Central and Southern China). La m´ethode utilise trois composantes principales : un outil de simulation de transport a´erien, un mod`ele d’estimation des surcoˆuts en fonction des retards, et un algorithme de s´election des routages. L’outil de simulation permet, ´etant donn´e un routage, de g´en´erer des sc´enarios relatifs a` ces routages. L’´evaluation des coˆuts de ces sc´enarios peut alors permettre d’estimer le coˆut moyen des diff´erents routages. Le but de l’algorithme de s´election est d’allouer dynamiquement aux diff´erents sc´enarios une quantit´e de simulations, pour prendre la meilleure d´ecision possible avec un nombre de simulations fix´e (une simulation pour un sc´enario prend environ 25 minutes d’apr`es les auteurs, une bonne allocation du temps de calcul est donc primordiale). L’algorithme utilis´e est une impl´ementation de l’algorithme OCBA [6] (Optimal Computing Budget Allocation). Une des difficult´es du probl`eme est bien sˆur la mise au point de l’algorithme de simulation. Les auteurs ont utilis´e l’outil de simulation discr`ete Arena, d´evelopp´ par Rockwell Automation, pour mod´eliser les vols.
Le probl`eme de l’´evaluation des programmes de courses de galop est assez similaire dans sa pr´esen-tation. On aimerait, parmi un ´eventail de programmes, pouvoir d´eterminer celui qui attirera le plus de partants de fa¸con robuste. Pourvu que l’on arrive a d´eterminer un bon mod`ele, une m´ethode bas´ee
`
sur la simulation peut tout `a fait ˆetre une option pour estimer l’attractivit´e d’un programme donn´e. A l’inverse du probl`eme de s´election de routages, en revanche, le m´ecanisme `a l’origine de la participation (les d´ecisions des entraˆıneurs) est difficile `a simuler et il est invraisemblable que l’on puisse obtenir une simulation fid`ele `a la r´ealit´. En ce qui concerne l’algorithme de choix, notre contexte est diff´erent puisque qu’une simulation de la participation aux courses d’une population de chevaux serait a priori rapide, et que le temps d’ex´ecution de l’algorithme de planification n’est pas critique, la planification
36
ˆ ´ ´
2.4. PLANIFICATION DE TACHES AVEC PERIODICITE
´etant effectu´ee une fois tous les trois mois. Nous serions plus int´eress´es par une fa¸con d’int´egrer l’´eva-luation par simulation des solutions au processus de recherche effectu´ par une m´eta-heuristique, pour le guider, ce qui sera etudi´ en section 5.7.
Les travaux d’apprentissage statistique pr´esent´es au chapitre 3 s’inscrivent dans cette d´emarche de gestion de l’incertitude, et le probl`eme de s´election de routes est celui qui, a` notre connaissance, se rapproche le plus du nˆotre dans sa probl´ematique d’estimation de la qualit´e des solutions.
2.4 Planification de tˆaches avec p´eriodicit´
La contrainte d’´ecart est, comme expliqu´ee en section 1.4.4.1, la contrainte la plus centrale et structurante de la planification des courses de galop. Cette contrainte impose a` chaque type de course (que l’on peut consid´erer comme des tˆaches) d’ˆetre planifi´e plusieurs fois par programme, plus ou moins r´eguli`erement. Le programme ´etant trimestriel, la planification est effectu´ee quatre fois par an. Ce processus de planification est donc r´eit´er´ chaque trimestre, tous les ans. Ainsi, notre probl`eme pourrait s’apparenter a` un probl`eme de planification cyclique, c’est-a`-dire avec un graphe des tˆaches infini et p´eriodique.
2.4.1 Probl`eme d’Ordonnancement Cyclique de Base
Un tel probl`eme est le Probl`eme d’Ordonnancement Cyclique de Base (BOCP). On se donne un ensemble T = T1, T2, …, Tq de tˆaches non pr´eemptives, et on note T (i, n) la n-i`eme ex´ecution de la tˆache Ti. On note pi la dur´ee de la tˆache Ti.
Les contraintes de pr´ec´edence se formulent alors sous la forme d’un ensemble P de triplets (Ti, Tj, k), avec k un entier naturel. Cet ensemble P d´efinit l’ordre
(Ti, Tj, k) ∈ P ⇒ (∀n ≥ 1) : T (i, n) < T (j, n + k)
c’est-a`-dire que la (n + k)-i`eme tˆache Tj doit ˆetre planifi´ee apr`es la n-i`eme tˆache Ti. Une solution au BOCP est alors un ensemble des dates de d´epart s(i, n) pour les tˆaches T (i, n) qui respecte
(Ti, Tj, k) ∈ P ⇒ (∀n ≥ 1) : s(i, n) + pi ≤ s(j, n + k)
Dans [7], Philippe Chr´etienne s’int´eresse aux valeurs maximales que peuvent prendre les s(i, n), lorsque l’on impose des deadlines, c’est-a`-dire des bornes sup´erieures pour les s(i, n) + pi.
37
ˆ ´ ´
2.4. PLANIFICATION DE TACHES AVEC PERIODICITE
Dans [8], l’auteur s’int´eresse a` la borne de Graham du probl`eme, c’est-a`-dire aux performances que l’on peut obtenir avec une heuristique de planification bas´ee sur une liste de priorit´es. Une g´en´eralisa-tion du probl`eme avec un nombre limit´e de machines (de tˆaches simultan´ees) est etudi´ee.
D’autres g´en´eralisations du probl`eme existent. Par exemple, dans [9], Alix Munier Kordon consid`ere que les contraintes de pr´ec´edence sont des quadruplets (Ti, Tj, ke, pe), o`u ke et pe sont des entiers relatifs et
(Ti, Tj, ke, pe) ∈ P ⇒ (∀n ≥ 1) : s(i, n) + pe ≤ s(j, n + ke)
Notamment, le temps a` respecter entre deux tˆaches n’est plus une dur´ee d’ex´ecution et peut varier suivant la contrainte. Elle ´etablit la periodicit´ de la solution « au plus tˆot » dans le cadre de cette g´en´eralisation.
Le BOCP peut ˆetre utilis´e pour mod´eliser une chaˆıne de production, dans laquelle la production d’un produit n´ecessiterait d’effectuer les tˆaches de T . Le but est donc de planifier chaque tˆache de T exactement n fois pour produire n produits.
Dans le probl`eme de planification des courses hippiques, on pourrait tout a` fait consid´erer que les diff´erents types de courses a` planifier sont les tˆaches de T , quitte a` inclure dans T plusieurs fois les mˆemes types de courses, pour les types de courses devant ˆetre le plus repr´esent´es dans un programme. Cependant, un des objectifs est de remplir au maximum le calendrier des r´eunions, il est alors impossible de fixer le nombre de courses de chaque type devant ˆetre pr´esent dans chaque programme. En ce qui concerne la contrainte d’´ecart, elle ´enonce qu’apr`es la planification d’une course du type Ti, on doit trouver une autre course de type Ti environ trois semaines plus tard. Elle n’interdit pas, en revanche, qu’il y ait d’autres courses de type Ti planifi´ees entre temps. Il est donc impossible d’´enoncer cette contrainte sous la forme T (i, n) < T (i, n + k), puisque la course situ´ee trois semaines (environ) apr`es la n-i`eme course de type Ti n’est pas la (n+k)-i`eme pour k fix´e. D’une mani`ere g´en´erale, la planification des courses de chevaux se distingue de beaucoup de probl`emes d’ordonnancement du fait de la variabilit´e de la liste des tˆaches a` planifier dans l’horizon de planification, et de l’impossibilit´e de mod´eliser la contrainte d’´ecart a` l’aide d’un graphe de pr´ec´edence fig´e.
38
ˆ ´ ´
2.4. PLANIFICATION DE TACHES AVEC PERIODICITE
2.4.2 Recurrent Job Shop
Le BOCP peut aussi ˆetre g´en´eralis´ pour donner le Recurrent Job Shop (RJS). L’´enonc´ du pro-bl`eme est le mˆeme que pr´ec´edemment, sauf que chaque tˆache Ti est associ´ee a` une unique machine Mi parmi la liste M = {1, . . . , m} des machines, capables d’ex´ecuter au plus une tˆache a` la fois. Dans [10], l’auteur ´etudie le probl`eme consistant a` d´eterminer la p´eriode minimale d’une solution p´erio-dique au probl`eme. Dans le cas o`u l’on relˆache les contraintes portant sur les machines, on se ram`ene au BOCP, et le probl`eme est polynomial. Dans le cas g´en´eral, le probl`eme est bien sˆur NP-difficile, puisqu’il contient le job shop comme sous-probl`eme. L’auteur d´emontre que le probl`eme reste NP-complet lorsque le graphe conjonctif des contraintes de pr´ec´edence (i.e. dans lequel les tˆaches T (i, n) sont r´eduites a` un seul point ti) est un circuit.
En raison de la difficult´e du probl`eme, des m´ethodes m´eta-heuristiques sont souvent utilis´ees pour trouver des solutions heuristiques de qualit´e au probl`eme. Dans [11], un recuit simul´e est utilis´e pour produire des ordonnancements pour plusieurs it´erations sur des instances de job-shop d’OR-Library. Les dur´ees des solutions produites pour 1, 2, ou 4 it´erations sont compar´ees avec une r´ep´etition des meilleures solutions connues pour une it´eration. Sur toutes les instances pr´esent´ees, le recuit produit une meilleure solution que la simple r´ep´etition de la meilleure solution connue pour une it´eration, et ce de mani`ere plus marqu´ee sur 4 it´erations que sur 2. Cela montre que le recuit simul´e est capable de tirer parti de la p´eriodicit´ du probl`eme pour produire de meilleures solutions.
Bien sˆur, comme pr´ec´edemment et pour les mˆeme raisons, le RJS ne permet pas de mod´eliser notre probl`eme de planification. En revanche, on peut esp´erer qu’un recuit simul´e pourra dans notre probl`eme ´egalement tirer parti de la nature p´eriodique de notre probl`eme, et rester efficace sur un horizon de planification important.

Table des matières

R´esum´e
Abstract
Liste des tableaux
Liste des figures
1 Presentation du probleme 
1.1 Contexte
1.2 Probl´ematiques et enjeux de l’´etude
1.3 Typologie des courses
1.3.1 Conditions d’ˆage
1.3.2 Distances
1.3.3 Cat´egories
1.4 Contraintes du probl`eme
1.4.1 Carri`ere d’un cheval
1.4.2 Contraintes dures de la planification
1.4.2.1 Code des courses au galop
1.4.3 Autres contraintes dures
1.4.4 Contraintes souples
1.4.4.1 Contrainte d’´ecart
1.4.4.2 Contrainte HR
1.4.4.3 Contrainte de Paires
2 Etat de l’art
2.1 Introduction
2.2 Planification d’´ev`enements sportifs
2.3 Gestion de l’incertitude
2.4 Planification de tˆaches avec p´eriodicit´e
2.4.1 Probl`eme d’Ordonnancement Cyclique de Base
2.4.2 Recurrent Job Shop
3 Apprentissage et ´evaluation d’un programme de courses 41
3.1 Introduction
3.2 Donn´ees d’apprentissage
3.3 Classification et r´egression
3.3.1 Donn´ees utilis´ees, caract´eristiques d’une course
3.3.2 D´efinition du probl`eme d’apprentissage
3.3.3 M´ethode de test
3.3.4 Classification par r´egression logistique
3.3.4.1 Enonc´e du probl`eme de classification
3.3.4.2 Pr´esentation de la m´ethode
3.3.4.3 R´esultats num´eriques de la r´egression logistique
3.3.4.4 Conclusion sur la r´egression logistique
3.3.5 Classification par gradient boosting
3.3.5.1 Pr´esentation de la m´ethode
3.3.5.2 R´esultats du gradient boosting
12
TABLE DES MATIERES `
3.3.5.3 Conclusion sur la classification par gradient boosting
3.3.6 Exploitation d’une classification
3.3.6.1 Mod`ele
3.3.7 Estimation de la fonction objectif
3.3.7.1 Ajuster les probabilit´es
3.3.7.2 Ajuster les gains
3.3.8 Gradient boosting regressor
3.3.8.1 R´esultats num´eriques
3.4 Evaluation d’un programme `a l’aide d’une simulation
3.4.1 Algorithme
3.4.2 R´eglage des param`etres
3.4.2.1 Algorithme SPSA
3.4.2.2 Impl´ementation de l’algorithme SPSA et r´esultats
3.4.3 Conclusion et perspectives sur la simulation
4 M´ethodes exactes pour g´en´erer une solution de planification 77
4.1 Introduction
4.2 D´efinition du probl`eme et notations
4.3 Mod`ele lin´eaire en variables 0-1
4.4 NP-difficult´e
4.5 G´en´eralisations du mod`ele
4.6 Limites du mod`ele lin´eaire en variables 0-1
4.6.1 Complexit´e pratique du mod`ele et conclusion
4.7 Remarques sur la planification par contraintes
5 M´ethodes approch´ees pour la planification des courses de galop 93
5.1 Heuristique inspir´ee du processus de planification manuelle
13
TABLE DES MATIERES `
5.1.1 R´ealisation manuelle du programme des courses de galop
5.1.2 Description de l’heuristique
5.1.3 D´etail du calcul des p´enalit´es du score d’une r´eunion dans l’heuristique gloutonne 96
5.2 Fonction d’´evaluation
5.3 Voisinages
5.4 RVNS
5.5 Recuit simul´e
5.6 R´esultats num´eriques
5.6.1 Recuit simul´e
5.6.2 RVNS
5.7 Optimisation bi-objectif `a l’aide d’un recuit simul´e modifi´e
5.7.1 Pr´esentation de l’algorithme de recuit simul´e multi-objectif avec priorit´e
5.7.2 Exp´eriences num´eriques
Conclusion 121
Bibliographie 127

Télécharger le rapport complet