Laboratoire d'informatique de l'École polytechnique

Seminar by G. Lucarelli: «A primal-dual approach for online scheduling with resource augmentation»

Speaker: Giorgio Lucarelli
Location: Room Flajolet, Alan Turing Building
Date: Mon, 13 Mar 2017, 15:30-16:30

Abstract: A well-identified issue in algorithms and, in particular, in online computation is the weakness of the worst case paradigm. Several more accurate models have been proposed in the direction of eliminating this weakness. Resource augmentation is one of these models which has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to it, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this context, we propose algorithms for online scheduling problems for minimizing variations of the total weighted flow time objective based on mathematical programming and a primal-dual scheme. Inspired by these algorithms, we present an online heuristic for non-preemptive scheduling sequential jobs, which outperforms standard scheduling policies as shown by an extensive campaign of simulations on instances obtained by real traces.