A Semi-dynamic Multiprocessor Scheduling Algorithm with an Asymptotically Optimal Competitive Ratio

In this paper, we consider the problem of assigning a set of n independent tasks onto a set of m identical processors in such a way that the overall execution time is minimized provided that the precise task execution times are not known a priori. In the following, we first provide a theoretical analysis of several conventional scheduling policies in terms of the worst case slowdown compared with the outcome of an optimal scheduling policy. It is shown that the best known algorithm in the literature achieves a worst case competitive ratio of 1 + 1/f(n) where f(n) = O(n ^2/3) for any fixed m, that approaches to one by increasing n to the infinity. We then propose a new scheme that achieves a better worst case ratio of 1 + 1/g(n) where g(n) = ⊝ (n/ log n) for any fixed m, that approaches to one more quickly than the other schemes.

Authors and Affiliations

1. Department of Information Engineering Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan

   Satoshi Fujita

Editors and Affiliations

1. Fachbereich 17, Mathematik und Informatik, Universität Paderborn, Fürstenallee 11, 33102, Paderborn

   Burkhard Monien  & Rainer Feldmann  & 

Reprints and permissions

© 2002 Springer-Verlag Berlin Heidelberg

Policies and ethics