*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 9
Dienstag, 19.09.2000, 17.30–17.50 Uhr, WIL C 133

The generalization of the algorithm LPT

György Dósa, Universität Veszprém

We investigate a well known problem of the scheduling theory: the scheduling of parallel independent machines, that is: How to distribute n task among m < n machines to minimize the overall finishing time. We generalize the classical algorithm called LPT of Graham, which is always scheduling the next task to the earliest time possible. In the general algorithm in each step we place k < n task at the same time optimally. If k = 1 then this is the original algorithm LPT. We investigate the efficiency of the general algorithm, and the numerical aspects, too. (Die Teilnahme an der Konferenz wird druch die Stiftung von Hans Pape, Dortmund, Dr.h.c. der Universität Veszprém unterstüzt.)