direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

07.02.2013 16:15
Gerhard Woeginger
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras