| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428744 | Information Processing Letters | 2008 | 5 Pages |
Abstract
We generalize and improve previous results of online preemptive deadline scheduling with preemption penalties. We consider both the preemption-restart and the preemption-resume models, and give new or improved lower bounds on the competitive ratio of deterministic online algorithms. In many cases the bounds are optimal when the job deadlines are tight. Our results show that the competitiveness varies linearly with the penalty factor.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
