Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Sgall, Jiri License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-695

Online Scheduling



We survey some recent results on scheduling unit jobs. The emphasis of the talk is both on presenting some basic techniques and providing an overview of the current state of the art. The techniques presented cover charging schemes, potential function arguments, and lower bounds based on Yao's principle. The studied problem is equivalent to the following buffer management problem: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The presented algorithms improve upon 2-competitive greedy algorithm, the competitive ratio is 1.939 for deterministic and 1.582 for randomized algorithms.

BibTeX - Entry

  author =	{Sgall, Jiri},
  title =	{{Online Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-695},
  doi =		{10.4230/DagSemProc.05031.20},
  annote =	{Keywords: online algorithms , scheduling}

Keywords: online algorithms , scheduling
Seminar: 05031 - Algorithms for Optimization with Incomplete Information
Issue date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI