30.10.2015 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2

Titel: Online Machine Covering: Exploiting Symmetries to Control Migration

Abstract:

Load balancing in parallel machines is a fundamental problem that has been studied extensively in the literature. We consider a version where jobs are revealed online one by one.  Our aim is to assign the jobs to a given number of machines in order to balance the load, more specifically, to maximize the load of the least loaded machine. In the classic online model decisions are irrevocable, which is unrealistic for several applications.

We consider a relaxed version proposed by Sanders et al., where a limited amount of jobs can be reassigned at the arrival of a new job. We are interested in understanding the trade-off between the quality of solutions and the amount of migrated jobs. In this talk I will introduce the problem and basic techniques. Then I will focus on the analysis of a simple greedy algorithm. Our main observation is that well chosen small perturbations of the processing times creates several types of symmetries in the solutions. This implies that solutions that are a priori very different are actually equivalent modulo these symmetries. We show how this property can be exploited algorithmically in order to find good solutions that are similar after the arrival of new jobs, thus yielding improved algorithms for this problem.

This is joint work with Waldo Galvez and Jose Soto.

Prof. Jansen

Diesen Termin meinem iCal-Kalender hinzufügen

zurück