TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 07.02.2013

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms

Prof. Dr. Gerhard J. Woeginger (Eindhoven University of Technology)

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.)

Date
Speaker
Location
Language
07.02.2013 16:15
Gerhard Woeginger
TEL 512
german/english

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe