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

Back to the research colloquium site.