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.

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 *)