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.
TIME AND MEMORY LIMITS (Python)
- Time: 1s on a 1GHz machine.
- Memory: 16,000 KB.
INPUT
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.
OUTPUT
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.
EXAMPLEs
EXAMPLE 1
input:
2 12 32 7 89 18 63 9 3
output:
117
EXAMPLE 2
input:
3 3400 1200 800 43 23 43 12 45 33
output:
3400
EXAMPLE 3
input:
3 3400 2500 45 34 1200 430 234 2300
output:
3500
COMMENTS
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 *)
Vous devez être connecté(e) pour résoudre ce problème.
L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.
Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.