Quand on a des milliers de calculs à répartir sur des centaines de machines, l'ordre dans lequel ces calculs sont effectués est critique, et si on s'y prend mal, on peut perdre beaucoup de temps, et donc d'argent et de ressources. On parle de problème d'ordonnancement, et ce problème est d'autant plus complexe que les machines peuvent être différentes, les temps de calculs difficiles à pronostiquer, etc
On a t tâches à exécuter dont on connaît le temps l'exécution (identique pour toutes les machines). On dispose de n>0 machines identiques pour exécuter ces tâches et on veut les exécuter dans n'importe quel ordre, mais on veut que cela termine rapidement.
Pour pouvoir répondre à ce genre de problèmes en temps réel, on utilise généralement des algorithmes gloutons, pas forcément optimaux mais qui ont de bonnes performances en pratique. Un algorithme glouton simple pour ce problème consiste à trier les tâches par ordre décroissant de temps de calcul, et à répartir ensuite les tâches dans cet ordre en les affectant à la machine ayant la moindre charge pour le moment.
Par exemple, prenons 5 tâches à répartir sur deux machines et ayant pour temps d'exécution 5 4 10 9 et 8. L'algorithme les trie donc d'abord de façon à obtenir 10, 9, 8, 5 et 4. Il affecte 10 à la première machine, puis 9 à la seconde, puisque celle-ci est moins chargée. Il affecte ensuite 8 à la seconde machine, toujours moins chargée, puis 5 et 4 à la première. Au final, la première machine aura un temps d'exécution total de 19 secondes, et la seconde un temps total de 17 secondes. Cette solution n'est toutefois pas optimale, par exemple on aurait pu donner 10 et 8 à la première machine, pour un total de 18 secondes, et 9, 5 et 4 à la seconde pour un temps total de 18 secondes également.
L'entrée est le nombre n de machines et la liste de taille t représentant le temps d'exécution de chacune des tâches.
La sortie sera le temps minimal nécessaire, tel qu'estimé par l'algorithme glouton expliqué dans l'énoncé, suivi d'un retour à la ligne.
entrée :
2 12 32 7 89 18 63 9 3
sortie :
117
entrée :
3 3400 1200 800 43 23 43 12 45 33
sortie :
3400
entrée :
3 3400 2500 45 34 1200 430 234 2300
sortie :
3500
Squelettes de codes :
(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les
mettre dans des variables, et afficher votre resultat final en sortie. *)
(* fonction pour separer les elements en entree
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
let res = ref [] in
let temp = ref "" in
for i = 0 to String.length chaine - 1 do
if chaine.[i]=' '
then
begin
res := !res @ [!temp];
temp := "";
end
else
temp := !temp ^ (String.sub chaine i 1);
done;
res := !res @ [!temp];
!res;;
(* On lit le nombre de machine a notre disposition et on la stock en n *)
let n = int_of_string (input_line stdin);;
(* On lit la liste des temps necessaires *)
let times = List.map int_of_string (split_spaces (input_line stdin));;
(* fonction pour afficher votre solution *)
let affiche_solution i =
print_int i;
print_newline();;
(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)
(* Debut de votre programme *)
(* Fin de votre programme *)