Loading...
Please wait, while we are loading the content...
Similar Documents
On the Speed Requirement for Optimal Deadline Scheduling in Overloaded Systems (2001)
| Content Provider | CiteSeerX |
|---|---|
| Author | Lam, Tak-Wah Ngan, Tsuen-Wan To, Kar-Keung |
| Description | In Proc. 15th International Parallel and Distributed Processing Symposium We consider the problem of scheduling jobs with deadlines in an on-line single-processor system. It is known for long that unless the system is underloaded, any on-line algorithm is not optimal in the sense that it may fail to match the optimal offline algorithm on the total work of jobs meeting their deadlines. In this paper, we extend this fact with two new lower bound results. First, we show that even if the on-line scheduler can use a processor s times faster than the offline scheduler, where s 1 is any real number less than the golden ratio (i.e. (1 + 5)=2 1:618), no online algorithm can be optimal. Furthermore, if we restrict our attention to on-line algorithms that decide at the release time of a job whether the job will be processed to meet its deadline, then the speed requirement for optimal on-line algorithms is at least 2. These lower bound results should be contrasted with the recent upper bound result [11] that with a two times faster processor, a simple extension of the earliest deadline first strategy (EDF) is optimal. |
| File Format | |
| Language | English |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Optimal On-line Algorithm Speed Requirement Bound Result Golden Ratio Recent Upper Bound Result Simple Extension Real Number On-line Algorithm Overloaded System On-line Scheduler Optimal Offline Algorithm Total Work Optimal Deadline Scheduling Deadline First Strategy Online Algorithm Release Time Processor Time Offline Scheduler On-line Single-processor System |
| Content Type | Text |
| Resource Type | Article |
