Dans ce talk, je ferai une introduction au domaine de l'ordonnancement non-clairvoyant et de la façon dont on obtient des résultats dans ce cadre très général qui a de nombreuses applications en algorithmique. Plus précisément, nous parlerons de nos derniers résultats sur la minimisation du temps de réponse maximal.
We consider the problem of nonclairvoyantly scheduling jobs, which arrive over time and have varying sizes and degrees of parallelizability, with the objective of minimizing the maximum flow. We give essentially tight bounds on the achievable competitiveness. More specifically we show that the competitive ratio of every deterministic nonclairvoyant algorithm is high, namely Ω(√n). But there is a simple batching algorithm that (1+ε)-processor O(log n)-competitive algorithm. And this simple batching algorithm is optimally competitive as no deterministic nonclairvoyant algorithm can be s-processor o(log n)-competitive for any constant s.