Un glouton exact que le cours ne traite pas : minimiser la somme des temps d'attente

Le glouton : la plus courte d'abord (règle spt, shortest processing time).

(* Somme minimale des temps d'achèvement. Précondition : durées > 0.
   Complexité : Theta(n log n). *)
let spt durees =
  let n = Array.length durees in
  let ordre = List.sort (fun i j -> compare durees.(i) durees.(j))
                        (List.init n (fun i -> i)) in
  let t = ref 0 and total = ref 0 in
  List.iter (fun i -> t := !t + durees.(i); total := !total + !t) ordre;
  !total

La démonstration, et elle tient en une ligne de calcul. Si l'ordre choisi est $\sigma (1),\dots ,\sigma (n)$, la somme des temps d'achèvement vaut

$$\sum _{k=1}^n\sum _{j=1}^k{d}_{\sigma (j)}=\sum _{j=1}^n(n-j+1)d_{\sigma (j)}.$$

La durée placée en $j$-ième position est donc comptée $n-j+1$ fois : la première tâche est comptée $n$ fois, la dernière une seule. Pour minimiser une somme de produits $\sum c_j{d}_{\sigma (j)}$ où les coefficients $c_j=n-j+1$ décroissent, il faut apparier les plus grands coefficients aux plus petites durées : c'est l'inégalité de réarrangement, et c'est exactement la règle spt.

Par échange, pour les mêmes raisons : si deux tâches consécutives $a$ puis $b$ vérifient $d_a>d_b$, les intervertir change la somme de $d_b-d_a<0$ — les autres tâches ne sont pas affectées, puisque la somme $d_a+d_b$ occupée est la même. Toute solution optimale est donc triée.

La vérification. Sur $20000$ instances tirées au hasard (jusqu'à six tâches), spt a été confronté à l'optimum obtenu en énumérant les $n!$ ordres : égal à chaque fois. Sur les durées $7,2,5,1,9$ :

Le glouton inverse coûte $82\%$ de plus que le bon.

Ce que cet exemple ajoute aux trois du cours. Il montre qu'un glouton se démontre parfois sans argument d'échange : ici, réécrire la fonction de coût sous la forme $\sum (n-j+1)d_{\sigma (j)}$ rend l'optimalité évidente. Le premier réflexe, devant un glouton à démontrer, est de réécrire le coût — et l'échange n'est que le recours quand cette réécriture n'existe pas.