Minimiser l'attente totale

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 7 — Algorithmes gloutons

É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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.