Probleme – Trois gloutons pour un même ordonnancement, et un seul qui répond à la question posée

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 16 — Algorithmes gloutons

Énoncé

$n$ tâches de durées $d_{i}$ et d'échéances $e_{i}$ , sur une machine unique, exécutées sans interruption. Le retard d'une tâche finissant à l'instant $t$ est $max (0, t - e_{i})$ .

On veut minimiser le retard maximal. Quel glouton ? Le démontrer.
Le glouton « la plus courte d'abord » convient-il ?
Comparer ce problème aux deux autres ordonnancements de ce chapitre.

Corrigé

1. Le glouton : par échéance croissante (règle edd, earliest due date).


(* Retard maximal minimal. Précondition : durées > 0.
   Complexité : Theta(n log n). *)
let edd durees echeances =
  let n = Array.length durees in
  let ordre = List.sort (fun i j -> compare echeances.(i) echeances.(j))
                        (List.init n (fun i -> i)) in
  let t = ref 0 and pire = ref min_int in
  List.iter (fun i ->
    t := !t + durees.(i);
    if !t - echeances.(i) > !pire then pire := !t - echeances.(i)) ordre;
  !pire

La démonstration, par échange. Soit $σ$ un ordre optimal. S'il n'est pas trié par échéance, il contient deux tâches consécutives $a$ puis $b$ avec $e_{a} > e_{b}$ . Notons $t$ l'instant où $a$ commence : $a$ finit en $t + d_{a}$ , et $b$ en $t + d_{a} + d_{b}$ . Après échange, $b$ finit en $t + d_{b}$ et $a$ en $t + d_{a} + d_{b}$ . Les autres tâches ne bougent pas.

Le retard maximal des deux tâches concernées vaut, avant l'échange,

$max (t + d_{a} - e_{a}, t + d_{a} + d_{b} - e_{b}),$

et après,

$max (t + d_{b} - e_{b}, t + d_{a} + d_{b} - e_{a}) .$

Or chacun des deux termes de la seconde expression est majoré par le second terme de la première : $t + d_{b} - e_{b} \leq t + d_{a} + d_{b} - e_{b}$ car $d_{a} > 0$ , et $t + d_{a} + d_{b} - e_{a} \leq t + d_{a} + d_{b} - e_{b}$ car $e_{a} > e_{b}$ . L'échange ne peut donc pas augmenter le retard maximal. En répétant — c'est un tri par bulles —, on transforme $σ$ en l'ordre edd sans jamais dégrader : edd est optimal.

Vérification : sur $20000$ instances tirées au hasard (jusqu'à six tâches), edd a été confronté à l'optimum obtenu en énumérant les $n!$ ordres. Aucun désaccord.

2. « La plus courte d'abord » ne convient pas. Sur $20000$ instances, elle s'est trompée $15720$ fois, soit $78, 6 %$ . Contre-exemple mesuré : durées $2, 1, 1, 8$ et échéances $3, 20, 21, 18$ . La règle spt donne un retard maximal de $1$ , l'optimum est $- 1$ — c'est-à-dire que toutes les tâches peuvent finir avant leur échéance, avec une marge d'une unité.

Pourquoi elle échoue : elle range selon une grandeur qui n'apparaît pas dans le critère à minimiser. Le retard dépend des échéances ; spt ne les regarde pas.

3. Les trois ordonnancements du chapitre, côte à côte. C'est le tableau à retenir.

Ce qu'on minimise	Le bon glouton	La preuve
somme des achèvements	durée croissante (spt)	réécriture du coût
retard maximal	échéance croissante (edd)	échange de deux voisines
pénalité des tâches en retard	pénalité décroissante	matroïde
poids des activités retenues	aucun	contre-exemple

Ce que ce tableau enseigne, et c'est la conclusion du chapitre. Les trois premières lignes portent sur la même machine et les mêmes tâches. Seule change la quantité à minimiser — et à chaque fois, le critère de tri change avec elle. Il n'existe pas de « bon ordre » d'exécution en soi ; il n'existe qu'un bon ordre pour une fonction de coût donnée, et la trouver demande à chaque fois une démonstration neuve.

C'est exactement pourquoi le cours exige qu'un glouton se démontre. Un ordre de tri paraît toujours raisonnable ; ce qui décide est de savoir si l'échange de deux voisins mal rangés améliore le coût qu'on a écrit, et non le coût qu'on avait en tête.

Toutes les mesures de ce chapitre, rassemblées. Chaque glouton y a été confronté à un oracle exhaustif écrit indépendamment, sur des instances petites et nombreuses.

Glouton	instances	désaccords	statut
activités, fin la plus tôt	$200000$	0	démontré
tâches unitaires, créneau le plus tard	$100000$	0	démontré (matroïde)
spt, somme des achèvements	$20000$	0	démontré
edd, retard maximal	$20000$	0	démontré
activités, celle qui commence le plus tôt	$200000$	$32229$	réfuté
activités, la plus courte d'abord	$200000$	$4842$	réfuté
tâches unitaires, créneau le plus tôt	$100000$	$66150$	réfuté
activités pondérées, fin la plus tôt	$20000$	$10127$	réfuté

Comment lire ce tableau, et c'est le dernier mot. Les quatre lignes du bas prouvent quelque chose : une faute. Les quatre du haut ne prouvent rien — un glouton peut être exact sur toutes les instances à cinq tâches et faux à six. La mesure réfute, elle ne démontre pas ; c'est le statut exact du test au chapitre chap:discipline.

Mais elle réfute vite, et c'est ce qui en fait le premier geste. La conduite est donc, dans cet ordre : (1) confronter à un oracle exhaustif sur des dizaines de milliers de petites instances — la plupart des candidats y meurent en dix secondes ; (2) si le glouton survit, le démontrer, par échange ou par réécriture du coût ; (3) si la démonstration résiste, chercher une garantie d'approximation, et la démontrer aussi.

Un avertissement sur le taux : « la plus courte d'abord » ne rate que $2, 4 %$ des instances. Sur un jeu d'essai de trente cas, il y avait moins d'une chance sur deux de le prendre en défaut — et il donne d'ailleurs l'optimum sur le jeu de onze activités du cours. Un générateur trop petit ou trop régulier laisse passer les fautes rares, et un glouton faux qui a survécu à trente essais est bien plus dangereux qu'un glouton faux qui échoue tout de suite.

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.