Connaissez-vous Rick Stone et Kirk Pinneo?

Chaque année, à la même époque (le mois de juillet), je me souviens que mon père et Meyer Harrus passaient plusieurs journées à résoudre un casse-tête que tous les directeurs d’école ont connu dans leur vie: préparer l’emploi du temps de l’année suivante. Gérer plusieurs dizaines de classes, de professeurs, des cours optionnels, des langues II, etc. ce n’est rarement simple. Et particulièrement lorsque certains enseignants ont leurs propres contraintes: untel qui ne veut pas travailler le mercredi, un autre qui enseigne dans un autre établissement, etc.

Bien sûr, il existe de nos jours des logiciels pour résoudre ce genre de casses-têtes. Même s’il n’existe pas d’algorithme parfait pour fournir une solution valide en un temps déterminé (c’est un problème NP complet), il existe des approches qui permettent d’optimiser les contraintes, voire de les accepter toutes si cela est possible, par approximations successives: on part d’une distribution non optimale, et on s’approche de l’optimum par petites modifications successives.

Lorsqu’il s’agit de gérer des calendriers aussi complexes que ceux des ligues de football, des championnats de formule 1 ou d’autres compétitions sportives, avec toutes les dépendances que cela comporte, ce casse-tête prend une dimension difficile à gérer seul. Rick Stone et Kirk Pinneo en ont fait un business, ayant conçu un logiciel d’optimisation des calendriers sportifs pour de telles compétitions. C’est le quotidien Le Monde qui s’en est fait l’écho ce mois-ci. Optimal Planning Solutions tient compte de contraintes parfois surprenantes, comme les dates de diffusion de certaines chaînes payantes, ne pas faire jouer plusieurs clubs géographiquement proches à domicile en même temps, ou optimiser les dates des derbys.

De l’emploi du temps d’un lycée aux championnats de football, il n’y a, au final, pas tant de différences…