Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Increasing Machine Speed in On-Line Scheduling of Weighted Unit-Length Jobs in Slotted Time
verfasst von : Jan Jeżabek
Erschienen in: SOFSEM 2009: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the following scheduling problem: Given a set of unit-length jobs characterized by release times, deadlines and weights an algorithm must pick at most one job for each unit of time with the goal of maximizing the total weight of the chosen jobs. An on-line algorithm is an algorithm which has no information about a job before its release time. In the basic version of this problem it is known that any on-line algorithm is outperformed by an optimal off-line algorithm by a factor of
${{1+\sqrt{5}}\over{2}}-\varepsilon$
on some instance. In this paper we examine the effect of increasing the on-line algorithm’s speed – that is the number of jobs chosen for each unit of time – and show that no speedup can fully compensate for the lack of complete information.