direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Vorträge 2013

Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
Prof. Dr. Gerhard J. Woeginger (Eindhoven University of Technology)
Thursday, February 7, 2013, 4:15 p.m., TU Hochhaus, 5th floor, room 512


We investigate the scheduling problem of preemptively minimizing the makespan for multiprocessor jobs on m identical parallel machines. Every job has a release date r, a length p and a width w from a given set W {1, 2, . . . , m}. The job enters the system at time r, and requests simultaneous processing on exactly w machines for a total of p time units. Preemption is allowed: the processing of a job can be interrupted at any moment in time, and can be resumed at any later moment on the same set of machines or on another set of machines. Every machine can process at most one job at a time. The goal is to minimize the largest job completion time, which is called the makespan of the schedule.

We are mainly interested in the online version of this problem where the jobs arrive over time. For any number m of machines, we characterize the width sets W for which there exists a 1-competitive online algorithm.

(This is joint work with Jiří Sgall from Prague.)


Manuel Sorge

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Research Colloquium

Algorithmik und Komplexitätstheorie