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.
Entrée
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.
Sortie
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.