–
February 16, 2017
The thesis is focused on the study of trade-offs in resource allocation problems. The first part of this thesis deals with the study of heuristic based approaches for the approximation of Pareto fronts. We propose a new stochastic local search algorithm for solving multi-objective combinatorial optimization problems. We embed our technique into a genetic framework and show that this method improves upon the existing Pareto local search algorithm on several instances of bi-objective and tri-objective quadratic assignment problem.
In the second part of this thesis, we focus on non-preemptive scheduling algorithms. Here, we first study the online problem of minimizing maximum stretch on a single machine. We present both positive and negative theoretical results. Furthermore, we study the problem of minimizing stretch/flow time on a single machine in a recently proposed rejection model. We show that there exists an O(1)-approximation ratio for minimizing the flow time. We further extend the idea used here to show that there exists an O(1)-approximation ratio for minimizing the average stretch on a single machine. Lastly, we study the weighted average flow time minimization problem in online settings. We present a mathematical programming based framework that unifies multiple resource augmentation. Then, we develop a scheduling algorithm based on the concept of duality and show that there exists an O(1)-competitive algorithm for solving the weighted average flow time problem on a set of unrelated machine! s. Furthermore, we extended this idea to the problem of minimizing weighted \ell_k norms of flow time on a set of unrelated machines
Jury:
- Oded Maler - Directeur de these
- Denis Trystram - Co-Directeur de these
- Adi Rosen - Rapporteur
- Monaldo Mastrolilli - Rapporteur
- Marie Christine Rousset - Examinateur
- Lothar Thiele - Examinateur
- Seffi Naor - Examinateur
- Daniel Vanderpooten - Examinateur
