EPFL/Projet-S2
Un article de Le wiki de 2 noisettes - noisette.ch.
Retour : EPFL
La première description de l'application que le projet vise à développer est disponible ici.
Le manuel de l'utilisateur est en cours de réalisation ici.
Sommaire |
Introduction
La gestion d'une semaine sportive est un travail long et fastidieux, et chaque professeur de sport se souvient des longues heures qu'il a passé à placer les élèves dans des groupes en fonction de leurs choix. Afin de mener à bien une telle organisation, les étapes suivantes sont appliquées :
- Contact avec les organisateurs des activités, pré réservation des infrastructures
- Inscription des élèves aux activités proposées
- Répartition des élèves dans les groupes
Après avoir analysé l'organisation de différents professeurs de sport, j'ai identifié plusieurs améliorations possibles lors des étapes précédemment définies. Mon projet vise donc à optimiser la gestion d'une semaine sportive, en terme de temps de travail du professeur mais aussi en terme de satisfaction des élèves vis-à-vis de leur répartition.
L'application développée va se pencher tout particulièrement sur l'inscription des élèves directement dans une base de données, pour éviter le travail de saisie que l'inscription sur une feuille pourrait engendrer, et sur le placement des élèves dans des groupes.
Bien que les technologies internet sont très bien adaptées à l'inscription des élèves, leur placement dans des groupes demande des connaissances un peu plus poussées en mathématiques. Mais j'expliquerai étapes par étapes comment ces objectifs ont été atteint, avec parfois quelques difficultés.
La première difficulté mise en avant est l'inscription des élèves à plus d'activités de nécessaires, par ordre de priorité. Le système de premier arrivé permier servi n'est vraiment pas bien adapté à la situation, car les activités sportives dans les écoles secondaires sont principalement pour les élèves défavoriser, ces élèves étant aussi les moins à l'aise avec les outils informatiques nécessaire pour l'inscription.
Timetable
- Semaine 1-2 : Rdv avec le cycle d'orientation du Belluard et de Pérolles pour la définition des besoins
- Semaine 3-4 : Modélisation de l'application
- Semaine 5-6-7-8-9-10 : Développement de l'application, manuel du développeur
- Semaine 11-12 : Tests, validations
- Semaine 13-14 : Ecriture du manuel de l'utilisateur, rapport
Conception
Il est tout d'abord important de définir quelques termes utilisés dans la suite du documents :
- Institution : chaque école ou organisation potentielle est désignée par le terme d'institution.
- Evénement : chaque semaine sportive sera représentée par un événement. Cette approche est simplement utile si on aurait besoin de gérer plusieurs événement en parallèles.
- Elève : l'élève est un utilisateur dont la seule action possible sera de s'inscrire à un événement.
- Administrateur : l'administrateur est la personne privilégiée qui gère les événements place les utilisateurs dans des groupes.
Etude des besoins
Les besoins ont été définis avec la participation de différentes institutions cités en "Remerciement". Mon idée était de tirer le maximum d'éléments communs afin de faire la base du programme, et d'ajouter les particularitées de chacunes en terme d'options configurables.
Les besoins communs suivantes ont été identifiés :
- Gestion des activités par demi-jour
- Inscription à une semaine type
- Inscription des élèves au plus simple
- Ne pas appliquer le concept de premier arrivé = permier servi
- Limitation des activités par année scolaire
- Priorité des élèves plus agés sur les plus jeunes
- Exportation des résultats sous forme de documents imprimables
Suivi des besoins particuliers de chacun
- Alternance des types
- Choix de remplacement en nombre de semaines supplémentaires à remplir
- Choix de remplacement en nombre d'activités supplémentaires
Afin de limiter le choix des élèves pour avoir un maximum de compatibilités entre les activités, il est nécessaire de gérer leur imbrications afin d'éviter une superposition. Plusieurs combinaisons d'activités sont possibles et doivent donc être traitées correctement :
- L'activité 1 comprend 2 groupes : A et B, dont les disponibilités sont définies dans le tableau ci-dessous :
| Activité 1 | Lundi | Mardi | Mercredi |
| Matin | Groupe A | Groupe A | Groupe A |
| Après-midi | Groupe B | Groupe B | Groupe B |
Les élèves participant au groupe A seront occupés les 3 matinées.
- L'activité 2 comprend 3 groupes : C, D et E, dont les disponibilités sont définies dans le tableau ci-dessous :
| Activité 2 | Lundi | Mardi | Mercredi |
| Matin | Groupe C | Groupe D | Groupe E |
| Après-midi | Groupe C | Groupe D | Groupe E |
Les élèves du groupe C seront occupés le lundi.
Les activités 1 et 2 sont donc incompatibles entre elles, c'est-à-dire que les élèves voulant faire ces 2 activités ne le pourront pas.
Vue globale
Schéma conceptuel global :
L'utilisateur
Cas d'utilisation pour l'utilisateur :
L'administrateur
sélectionner ou insérer un nouvel événement, puis -> activités, groupes, inscription
Cas d'utilisation pour l'administrateur :
Résolution des groupes
Selon notre modèle d'inscription, les élèves vont s'inscrire à plusieurs activitées par ordre de préférence, indépendamment des horaires des groupes disponibles pour une activité. Mais comme au final les élèves vont être répartis dans les groupes des activités, une procédure de placement des élèves dans leurs groupes respectifs est nécessaire.
D'après les connaissances à disposition sur les différentes méthodes existantes pour répartir les élèves dans des groupes de manière optimale en fonction de leurs choix, la programmation linéaire se place en bonne candidate.
Il nous faut donc exprimer les choix des élèves et les contraintes du système par un ensemble d'équations linéaires. Nous identifierons les variables du système et une fonction d'utilité que nous essayerons de maximiser sous des contraintes paramétrables et quantifiable.
Les variables
Les variables de notre système d'équation vont nous permettre de placer un élève dans un groupe. Elles seront donc constituées de toutes les pairs élève/groupe possible. Si un élève s'inscrit à une activité qui contient 2 groupes, l'élève aura 2 variables pour représenter ce choix, une par groupe.
Une fois le système résolu, il nous faudra retrouver la correspondance entre la variable et sa signification, c'est-à-dire la pair élève/groupe qu'elle représente. Pour cela une notation pour les variables est introduite : la variable sera composé de la concaténation l'identifiant de l'élève et du groupe qu'elle représente, les deux numéros étant séparés par un caractère prédéfini. Par exemple eXXXgYYY signifie l'élève XXX pour le groupe YYY.
Les variables du système seront binaire : elles vaudront 1 si l'élève participera à l'activité de ce groupe, 0 sinon. Notons au passage que cette contrainte de nombre entier restreindra drastiquement notre éventail d'algorithme utilisable.
La fonction objectif
La fonction objectif est la fonction qui sera maximisée sous les contraintes définies ci-dessous. Elle devra donc faire ressortir le fait que le permier choix d'un élève est plus important que les autres.
L'idée est de travailler sur la pondération des variables utilisées dans la fonction objectif afin de faire ressortir l'importance des choix : le premier choix aura un pondération plus importante que le deuxième et ainsi de suite. De ce fait l'utilité apporté si l'élève est placé dans un groupe de son premier choix sera plus grande que si l'élève est placé dans son deuxième choix. On pourra aussi modifier les pondération de telle manière que si le système préfère placer les élèves dans leurs 2ème et 3ème choix plutot que dans leurs 1er et 4ème choix, mais cette analyse de sensibilité sort du cadre du projet actuel.
Finalement la fonction objective sera la somme de toutes les choix des élèves pondérées comme décrit ci-dessus.
Les contraintes
Les contraintes sont basées principalement sur les horaires des groupes et sur le nombre de place par groupe. Ces deux types de contraintes sont dynamiques, c'est-à-dire que l'administrateur peut à tout moment augmenter la capacité d'un groupe ou ajouter un groupe à une activité. A celles-ci s'ajoute des contraintes statiques, sur lesquelles l'administrateur ne peut pas agir, mais qui sont nécessaire pour garantir le bon placement des élèves dans les groupes.
Les contraintes dynamiques suivantes ont donc été identifiées :
Contraintes de place
Cette contrainte permet de limiter le nombre maximal d'élèves pour un groupe donnée. Elle permet par la même occasion de forcer un nombre minimum d'élèves à participer à cette activité, en allant chercher des élèves ayant choisit cette activité dans leur derniers choix si nécessaire.
Formellement : Pour chaque groupe d'une activité, la somme de tous les élèves inscrits à cette activité est inférieure ou égale au nombre maximum de participants, et suppérieure ou égale au nombre minimum de participant.
Contraintes de participation
Cette contrainte controle que les élèves ne participe pas à plus d'une activité par demi-jour.
Formellement : Pour chaque demi-jour de l'événement, pour tous les élèves, la somme de des groupes auxquels l'élève peut être potentiellement inscrit est inférieure ou égale à 1. Dans cette contrainte, l'égalité strict devraient être appliquée, mais si un élève pour une raison ou pour une autre ne pourrait pas être placé dans des groupes pour recouvrir toute la semaine, la résolution d'équation échouerait. Nous préférerons donc une contrainte souple ici, et après la résolution d'équation nous effectuerons un test pour controler si tous les élèves ont bien une activité tous les demi-jours.
Contraintes d'alternance des types
Cette contrainte, facultative, permet de faire en sorte que les élèves ne peuvent pas faire 2 activités du même type durant l'événement.
Formellement : Pour tous les élèves, la somme de tous les groupes d'activités du même type est inférieur ou égale à 1. Là de nouveau l contrainte souple est pour permettre une convergence de l'algorithme même en cas de solution partielle.
Contraintes de non-répétabilité
Cette contrainte empêche l'élève de participer plusieurs fois à une même activité, en se plaçant dans des groupes différents.
Formellement : Pour chaque élève, pour chaque activité, la somme des groupes auxquel l'élève peut participer est inférieur ou égale à 1.
Contraintes d'entier
Comme expliqué ci-dessus, les variables de ce système doivent être entière, plus précisément 0 ou 1. Nous devons donc introduire cette contrainte d'entier dans le système, ou alors utiliser un algorithme de résolution qui ne prend en compte que les nombre entiers.
Implémentation
Générale
- Pourquoi LAMP
- Utilisation de design patterns connus :
- Introduction aux patterns PHP (réf 1, réf 2)
- Observer (réf 1, réf 2) : assure qu'une interface graphique soit bien mise-à-jour lors d'un changement de valeur.
- Composite (réf 1, réf 2) : fournit un méchanisme pour grouper plusieurs composantes dans une seule interface au runtime.
- Visitors (réf 1, réf 2) : moyen très natruel d'effectuer des opérations sur une structure de données
- Factory
- Skeleton
- Abstract class et implementations
- Séparation des données (core interface) de l'interface (GUI interface) (réf) en utilisant un manager de templates (SMARTY?)
Technologie
PHP
- Sessions PHP
La nature du protocole HTTP ne permettant pas le suivi des connexions des utilisateurs, une couche logiciel doit remplir ce rôle. En PHP, elle se nomme SESSION, et permet d'associer une session unique à un utilisateur, qui la retrouvera à chaque connexion sur le site.
Ces sessions permette de définir des variables persistantes -> variables globales -> authentification
- PEAR::Spreadsheet
- FPDF
Apache
- URL rewriting
Les URL sont utilisées pour passer les paramètres aux pages affichées
Programmation linéaire
- lp_solve
Une librairie, nommée lp_solve, rempli toutes les attentes pour la résolution des équations linéaires. Cette librairie est open-source, distribuée sous licence LGPL (Less Gnu Public License)
L'utilisateur
Etape de sélection de activités à préférences
La machine d'état est gérée par 2 variables :
$STEP et $INIT.
$STEP gère effectivment la fts, alors que $INIT enregirstre les changements d'états et permet une initialisation des variables dans le nouvel état
L'administrateur
Conclusion
Améliorations possibles
- Gestion des affinités inter élèves pour leur répartition.
- Optimisation des pondérations de la fonction objectif (éventellement choix + année plutôt que choix * année afin de réduire l'écart entre les années)
Sécurité du système
- Différents type d'attaque (injection SQL/email, XSS, string format)
- Audit du code (Ecyware GreenBlue Inspector - Integrated Web Analyzer Environment)
Remerciements
La réalistaion de ce projet n'aurait pas été possible sans la collaboration d'Omne computers, qui a mis à diposition toutes les ressources matériels dont j'avais besoin (serveu internet, bande passante, ...) ainsi qu'aux cycles d'orientations du Bélluard et de Pérolles, qui ont daigné jouer les cobayes en me confiant la gestion de leurs semaies sportives et culturelles.
Ressources
UML
TODO
A implémenter
-
Implémenter les options de sauvegarder et de restorer
- Durée d'un groupe plus configurable que matin/après-midi
- Sexe de l'élève
A fixer
- Ajouter un nom par défaut à un groupe si aucun nom
- "appliquer à tous les groupes" de l'événement uniquement
-
Disponibilités pour tous si rien mis.
RÀV
exec("(touch ." . $id . ".lock; ./lp_slove in." . $id . ".txt > out" . $id . ".txt; rm ." . $id . ".lock)&");
Decorator pattern : http://www.phppatterns.com/docs/design/decorator_pattern Utilisé pour ajouter des fonctionnalités @runtime à un objet (genre le tri)
-> Objects (basé sur les itérateurs), NameSortObjects, TypeSortObjects, ...
