Minimiser l'attente totale

Algorithmes gloutons · niveau 2

Énoncé

$n$ clients dans une file d'attente requièrent des temps de service $t_{1}, \dots, t_{n}$ . Proposer un ordre de passage qui minimise le temps d'attente cumulé et en faire la preuve par échange.

Corrigé

Le critère optimal consiste à servir les clients par durées de service croissantes (les plus courts d'abord). Preuve d'échange : Supposons qu'il existe un ordre optimal dans lequel deux clients successifs $a$ et $b$ vérifient $t_{a} > t_{b}$ ( $a$ passe juste avant $b$ ). Si l'on permute ces deux clients, les temps d'attente de tous les autres clients restent inchangés. La somme des temps d'attente des deux clients concernés passe de $t_{a} + (t_{a} + t_{b}) = 2 t_{a} + t_{b}$ à $t_{b} + (t_{b} + t_{a}) = 2 t_{b} + t_{a}$ . La variation globale de l'attente est de $(2 t_{b} + t_{a}) - (2 t_{a} + t_{b}) = t_{b} - t_{a} < 0$ . La somme des temps d'attente diminue donc strictement suite à la permutation, ce qui contredit l'hypothèse d'optimalité de l'ordre initial. Ainsi, l'ordre optimal doit trier les clients par durées croissantes.

Énoncé

Corrigé

Exercices semblables