L’ordonnancement consiste à planifier des tâches (à réaliser selon certains objectifs) sous contraintes de ressources (matérielles et humaines), contraintes temporelles et enchaînements entres les tâches (processus). Ce problème est bien connu en Optimisation, et sa résolution exacte (c’est-à-dire trouver l’optimal) requiert un temps qui augmente exponentiellement avec la taille du problème à traiter (c’est ce qu’on appelle un problème NP-Complet, « NP » pour « Non Polynomial » donc exponentiel).
Dans l’industrie, les tailles à traiter sont généralement conséquentes (grosse usine, gros volumes / enjeux journaliers), voire énormes (car si on investit dans un logiciel, autant qu’il puisse calculer sur tout l’encours sur plusieurs semaines). Les résolutions utilisant une approche exacte optimale ont alors un temps de réponse de plusieurs minutes, voire plusieurs heures. De plus en plus de demandes client contiennent également une exigence temps réel, c’est-à-dire qu’il faut recalculer une solution à chaque détection d’aléa, et les temps de calculs des modèles optimaux deviennent donc incompatibles avec une utilisation en temps réel.
Historiquement, ces problèmes sont traités à l’aide de programmation mathématique (PL/MIP ou PPC), qui souffrent d’une explosion combinatoire due à l’aspect discret du problème (contraintes disjonctives). Pour diminuer les temps de réponse, on peut restreindre la recherche de solutions, mais même avec des stratégies très ciblées pour un métier donné, les algorithmes utilisés par les solveurs qui garantissent une exactitude (et donc une optimalité de la réponse) consomment trop de temps. De plus, en cas d’aléas fréquent et/ou conséquents, une situation optimale à un instant T sera très vite obsolète, voire risquée si elle suppose des temps finalement irréalisables (car constamment soumis à des aléas).
Le composant LP-Scheduler d’EURODECISION est un solveur de problèmes d’ordonnancement qui vise à appliquer des stratégies de recherche de solutions simples, mais rapides, permettant ainsi de multiplier / paralléliser les recherches et converger au plus vite vers la meilleure solution métier. On perd l’optimalité absolue, mais on gagne énormément en performance, et surtout en capacité d’introduction de nouvelles heuristiques métiers.
Au lieu de laisser explorer toutes les possibilités théoriques du modèle mathématique, on explore quelques combinaisons pratiques qu’on va définir explicitement avec des règles métier. On construit la solution en appliquant des leviers métiers (des « heuristiques ») bien définis (et donc explicables, reproductibles, avec une complexité connue, et extensibles au besoin). La partie analytique (respect des capacités, non-chevauchements, contraintes temporelles) étant assurée par le cœur de calcul du solveur.
La plupart du temps, une solution est jugée « bonne » ou non par un opérateur métier utilisant le moteur : ce dernier s’attend à ce que le logiciel propose une solution qu’il considère être de « bon sens », et qu’elle respecte des contraintes opérationnelles parfois cachées ou difficilement exprimables analytiquement. Remettre les heuristiques métiers au centre de la résolution a permis de satisfaire des clients d’EURODECISION exigeant une réponse du moteur d’optimisation en quelques secondes.
