Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Better bounds for online scheduling

Albers, Susanne

MPI-I-97-1-009. March 1997, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We study a classical problem in online scheduling. A sequence of jobs must be
scheduled on $m$ identical parallel machines. As each job arrives, its
processing time is known. The goal is to
minimize the makespan. Bartal, Fiat, Karloff and Vohra gave a
deterministic online algorithm that is 1.986-competitive.
Karger, Phillips and Torng generalized the
algorithm and proved an upper bound of 1.945. The best lower bound currently
known on the competitive ratio that can be
achieved by deterministic online algorithms
it equal to 1.837. In this paper we present an improved deterministic online
scheduling algorithm that is 1.923-competitive, for all $m\geq 2$.
The algorithm is based on a new scheduling strategy, i.e., it is not
a generalization of the approach by Bartal {\it et al}. Also, the algorithm
has a simple structure. Furthermore,
we develop a better lower bound. We prove that,
for general $m$, no deterministic online scheduling algorithm can be
better than \mbox{1.852-competitive}.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-009.ps181 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Albers, Susanne},
  TITLE = {Better bounds for online scheduling},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-009},
  MONTH = {March},
  YEAR = {1997},
  ISSN = {0946-011X},