Advertisement
Published in:
2009 | OriginalPaper | Chapter
Increasing Machine Speed in On-Line Scheduling of Weighted Unit-Length Jobs in Slotted Time
Author : Jan Jeżabek
Published in: SOFSEM 2009: Theory and Practice of Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.