Commençons tout d’abord par formaliser le critère à optimiser, c’est à dire l’encours de surface occupée. Cette surface-temps peut s’exprimer de deux façons différentes :
La surface sous la courbe du graphique 1 correspondant à l’ordre de rangement 1, 2, 3 ...7. Si on note t1, t2 ...t7 les temps de mise en stock et l1, l2, ...l7 le nombre de palettes livrées, la surface s’exprime par :
S = t1 ´ (l1+ l2+ l3+...+ l7) + t2 ´ (l2 + l3 +..+l7) + ...+t7´l7
Cette expression peut également s’écrire S = l1 ´ t1 + l2´(t1+t2) + l3 ´(t1 + t2 +t3) +...+ l7 ´ ( t1 + t2+...t7) = l1´f1 + l2 ´ f2 + ...l7´ f7 où fi représente la date de fin de l’opération i pour l’ordre choisi. En effet f2 = t1 + t2 est bien la date de fin de 2 (deuxième tâche), f3 = t1 + t2 + t3 la date de fin de 3... Il s’agit donc bien d’une mesure de l’encours de surface occupée : place occupée ´ temps d’occupation.
Graphique 1
C’est cette quantité qu’il faut rendre minimum en trouvant l’ordre d’exécution des tâches approprié.
Il est possible de comparer les deux solutions proposées dans le tableau 1 ci-dessous.
Tableau 1
Sur cet exemple la règle de la libération prioritaire des plus grandes surfaces s’avère être la plus efficace. Mais dans d’autres circonstances, en particulier si les volumes sont égaux ou voisins (livraisons de camions complets par exemple) c’est bien dans l’ordre des temps croissants de mise en stock qu’il faut procéder. Les deux règles ne conduisent généralement pas à la même séquence de tâche. Quand faut-il appliquer l’une ou l’autre ?
Nous allons montrer que cet antagonisme peut être résolu. La règle idéale est la suivante : Il faut réaliser les tâches dans l’ordre des ratios « temps / volume » croissant*, ce qui est en cohérence avec les deux règles énoncées. Ce ratio s’interprète ici comme le temps moyen de mise en stock d’une palette d’une livraison. Le tableau 2 présente cette solution qui effectivement améliore le critère d’encours retenu : 6932 palettes-minutes occupées contre 7042 dans la meilleure solution précédente.
Tableau 2
Le graphique 2 présente la comparaison de 3 solutions (ordre initial, par volume décroissant, optimum). C’est donc la courbe bleue qui « emprisonne » la surface la plus faible sous elle.
Graphique 2
La démonstration mathématique de l’optimalité de l’ordre proposé est assez simple, il repose sur la remarque qu’un ordre qui ne respecterait pas dans sa séquence la règle temps/volume croissant entre deux tâches consécutives pourrait être amélioré par leur permutation.
Mais on peut se convaincre géométriquement du bien fondé de cette règle. Comme nous l’avons remarqué, c’est l’aire sous la courbe de la place occupée qui doit être la plus faible possible. Pour ce faire, il faut que cette courbe décroissante, valant 0 au bout de 132 minutes décroisse (se creuse) le plus rapidement possible. Or la vitesse de décroissance après la réalisation d’une tâche i n’est autre que le rapport li / ti. Pour « creuser » rapidement la courbe il faut commencer par les plus forts ratios li / ti et donc ordonner suivant li / ti décroissants ou les ti / li croissants.
Philippe Vallin
*Cette règle est connue sous le nom de règle de SMITH
