21.04.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

Titel: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

Abstract:

Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time. The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type. We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance). We analyze a simple modification of the FIFO strategy and show the competitiveness to be $\Theta(\sqrt{n})$, which is optimal for ``greedy-like'' algorithms. We will then also consider a smoothed analysis of the competitiveness. The smoothed competitiveness turns out to only be $O(\varepsilon^{-2} \log^{^2} n)$ when processing times $p_j$ are independently perturbed by adding a random value uniformly drawn from $[-\varepsilon p_j, \varepsilon p_j]$, $0 < \varepsilon < 1$. The talk is based on joint work with Manuel Malatyali and Sören Riechers.

Prof. Jansen

Diesen Termin meinem iCal-Kalender hinzufügen

zurück