Challenge IT45 (Print. 2021)
Problème d’affectation d’employés
1 Introduction
Le challenge IT45 vise à confronter les étudiants à un problème de recherche opérationnelle concret afin
qu’il puisse appliquer et adapter les techniques qui auront été vues en cours.
Il sera évalué suivant 3 critères :
— Le travail réalisé par l’équipe qui sera mesuré en termes de performances obtenues pour les jeux
d’essais utilisés pour l’évaluation, mais également en considérant l’originalité de la démarche, la
rigueur du travail accompli, ainsi que la clareté des codes sources,
— Un rapport de quelques pages qui explique la problématique traitée et la méthode adoptée pour
solutionner le problème considéré,
— Une soutenance d’une dizaine de minutes au cours de laquelle vous exposerez votre travail.
2 Problème d’optimisation
Un SESSAD est un centre proposant des Services d’accompagnement d’Education Spécialisée A Domicile.
C’est une structure regroupant des intervenant.e.s (ou interfaces) qui ont pour rôle d’accompagner des
personnes ayant des déficiences visuelles ou auditives à des formations pour leur traduire le contenu des
formations. Lorsqu’une mission est confiée à une personne interface, elle doit se rendre depuis le SESSAD
sur le lieu de formation. L’interface fait sa prestation de traduction pour la formation qui peut durer
plusieurs heures. Ensuite, l’interface réalise sa mission suivante. A la fin de sa journée, l’interface revient
au centre SESSAD.
Les interfaces ont des compétences soit en langage des signes ou en codage LPC, soit les deux. Les personnes
à accompagner doivent l’être par une interface qui a la bonne compétence : langage des signes ou codage
LPC. Ensuite on a des référentes pour des formations particulières, par exemple « menuiserie » qui devront
être associées prioritairement dans le cas où la personne à accompagner suit une formation menuiserie.
On parle alors de spécialité. Une interface qui n’a pas la spécialité attendue pour une formation peut
quand même être affectée à cette formation, même si il est préférable d’affecter une interface ayant cette
spécialité.
Les interfaces peuvent être à temps plein (35h) ou à temps partiel (24h). Elles doivent avoir si possible
une pause d’1 h à midi pour se reposer et se restaurer. L’amplitude horaire de la journée est de 12h, c’est à
dire que si la journée commence à 6h00 du matin, la journée doit se terminer avant 18h, mais une journée
de travail ne peut pas durer plus de 8h00. De plus il faut minimiser les déplacements et les équilibrer entre
les différents employés.
1
3 Travail à réaliser
— Objectif : on demande de concevoir une méthode de résolution qui permette de trouver la meilleure
solution possible. Une solution sera valide si toutes les missions peuvent être assignées à des inter-
faces ayant la bonne compétence. Pour l’objectif à optimiser, on pourra tenir compte de la distance
parcourue, de l’écart type de la distance parcourue entre employés et du nombre de spécialités
satisfaites. La fonction objectif pour une solution s sera la suivante :
min z = 0.5 ∗ (moyd(s) + ecartd(s)) + 0.5 ∗ fcorr ∗ penalite(s)
avec :
- moyd(s)=distance moyenne parcourue par les employés pour s
- ecartd(s)=ecart type des distances des employés pour s
- fcorr = facteur de corrélation = moyenne de toutes les distances =
∑
i,j
dij
nbrmissions
- penalite(s)=nombre de spécialités non satisfaites
— Instances de résolution : des instances de problème de différentes tailles seront proposées pour
l’évaluation de votre méthode
— Temps limite : un temps limite d’exécution de votre algorithme devra être intégré à votre pro-
gramme. Lorsque le temps limite est dépassé, l’algorithme devra s’arrêter et afficher la meilleure
solution trouvée jusque là.
— Etapes du projet : deux étapes principales seront envisagées pour le projet.
1. Analyse, conception : la 1ère étape aura pour objet d’analyser le problème considéré et de
proposer un algorithme de résolution. C’est dans cet étape qu’il faudra proposer un modèle
pour le problème concerné qui pourra comprendre le codage des résolutions, les opérateurs de
voisinage, l’algorithme de la méthode de résolution, etc.... Cette 1ère étape devra se traduire
par la rédaction d’un dossier d’analyse/conception du problème d’environ 2 pages, à rendre d’ici
fin mai.
2. Développement : dans cette 2ème phase, il faudra développer l’algorithme imaginé pendant
la phase de conception en C/C++ ou java. En fonction des résultats que vous obtiendrez en
testant les différentes instances, vous aurez ensuite à régler les paramètres de votre algorithme
pour l’améliorer. Cette 2ème phase devra se terminer avant le 15 juin. Les livrables de cette
phase sont :
(a) une archive de votre projet contenant un README.md permettant d’expliquer comment
compiler et exécuter votre programme. Votre projet doit pouvoir s’exécuter sur une plate-
forme linux.
(b) un script bash nommé ’build’ permettant de compiler votre projet et un script bash nommé
’run’ permettant d’exécuter votre projet
(c) le rapport au format pdf
2


















































































































































学霸联盟