Optimiser l’organisation d’un planning

Même pendant les vacances, on peut réfléchir à optimiser un travail futur. Voici un exemple que je viens de mettre en place.

Problématique

Il arrive souvent d’avoir à faire de l’organisation de planning. Typiquement, la problématique est la suivante :

On se donne une liste de plages horaires.
On se donne une liste de personnes qui ont des préférences/contraintes.

Je suppose que les deux listes sont de même tailles, taille que je note N. (ie tout le monde aura une place, et il ne restera pas de places vacantes)

Là, on a trois catégories d’organisateurs

Ceux qui trouve quelqu’un a qui déléguer le travail
Ceux qui y vont manuellement : « Alors, lui il veut ca, bon , on le mets, et lui… mince la même chose… »
Ceux qui vont réfléchir un peu

Je décide d’appartenir à cette 3ème catégorie.

Priorité

Plaçons-nous dans le cas où on doit placer une personne par jour de la semaine. Je vais envoyer à chaque personne un petit fichier contenant ceci :

[nom]
Lundi=0
Mardi=0
Mercredi=0
Jeudi=0
Vendredi=0

Les valeurs représentent les priorités. Je fixe une petite règle du jeu (pour que toutes les personnes soient égales). Par exemple :
Chaque personne peut utiliser zéro fois ou une fois seulement chacune des valeurs suivantes : 1,2,3. Les autres seront des zéros (0).
Toto me renverra ce fichier par ex :

[Toto]
Lundi=1
Mardi=0
Mercredi=3
Jeudi=2
Vendredi=0

Méthode déterministe

Une méthode évidente est, une fois que l’on a récupéré les 5 fichiers, de passer en revue toutes les arrangements possibles. Le nombre d’arrangement est facile à déterminer :

$N!$

Pour ceux qui se souviennent de leurs cours de maths du secondaire, c’est l’arrangement $A_n^p$ où $p=n$ :

$A_n^p = \frac{n!}{(n-p)!} = n(n-1)...(n-p+1)$

On peut retrouver ce résultat simplement avec le raisonnement suivant, on a $N$ possibilité pour le premier choix, puis $N-1$ etc.

Dans notre exemple, $5!=120$ , ce qui est abordable à toutes les machines. Mais dès que l’on passe la 20ène, le nombre est déjà plus conséquent. Il serait donc bon d’utiliser une autre méthode pour les cas de grosses organisations.

Approche statistique

Plutôt que de passer en revue « naïvement » toutes les possibilités, nous allons utiliser un algorithme de Monte-Carlo et nous promener dans l’espace des possibilités. J’utiliserai ce que l’on appelle l’algorithme de Metropolis, ça devrait être largement suffisant. Pour plus de détails, je vous renvoi au cours de Pascal Viot.

L’idée est de définir au système un potentiel et de trouver le minimum global de ce potentiel (en évitant au mieux les minima locaux). Définissons donc le Hamiltonien (énergie) suivant :

$\Large{ H(\{j_i\}) = - \sum_{i=0}^N f_i(j_i) }$

où $f_i(j_i)$ désigne la priorité de la personne i pour la date $j_i$ . L’indice i permet de garder en mémoire que la collection des $\{ j_i\}$ ne doit pas comporter deux éléments identiques (deux personnes ne peuvent avoir le même rendez-vous). La notation est un peu subtile, mais une autre écriture plus univoque aurait demandé une double sommation et l’utilisation d’un terme répulsif (delta de Dirac) et aurait finalement compliqué l’affaire.

Le signe moins permet (dans mon cas) d’avoir des énergies toutes négatives ou nulles. On va donc bien chercher un minium.

L’algorithme de Metropolis est le suivant.

On se donne une configuration de départ. On calcule son énergie avec notre Hamiltonien : $U_{init}$

On échange les dates de deux personnes et on calcule à nouveau l’énergie $U_{fin}$ . Deux cas se présentent :

Si $U_{fin} < U_{init}$ , on adopte la nouvelle configuration plus favorable.
Sinon, on tire au hasard un nombre entre 0 et 1, que l’on compare à $e^{-\beta(U_{fin} - U_{init})}$ et on acceptera ou non la configuration selon. Ceci nous permet de sortir d’un minimum local.

On va enregistrer l’état de plus basse énergie trouvé et on considérera que c’est notre optimum.

Implémentation

J’ai implémenté ce petit algorithme en python. OK, coté performance, il y a sans doute mieux, mais disons que c’était vite fait. Par ailleurs, je ne connais pas de bibliothèque équivalente à ConfigObj en C++ (ou en C), si vous connaissez, n’hésitez pas !

Par ailleurs, j’ai implémenté aussi le méthode déterministe (ce qui, accessoirement, me permet de valider mon code).

Je mets à disposition le code à cette adresse. (GPLv2)

A l’heure où j’écris ces lignes, il me reste à gérer les cas où plusieurs possibilités existent pour un même taux de satisfaction.