Please use this identifier to cite or link to this item:
|Title:||Competitive on-line scheduling with Level of Service|
|Authors:||Chang, E.-C. |
Level of service
|Citation:||Chang, E.-C., Yap, C. (2003). Competitive on-line scheduling with Level of Service. Journal of Scheduling 6 (3) : 251-267. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1022904408360|
|Abstract:||Motivated by an application in thinwire visualization, we study an abstract on-line scheduling problem where the size of each requested service can be scaled down by the scheduler. Thus, our problem embodies a notion of "Level of Service" that is increasingly important in multimedia applications. We give two schedulers FirstFit and EndFit based on two simple heuristics, and generalize them into a class of greedy schedulers. We show that both FirstFit and EndFit are 2-competitive, and any greedy scheduler is 3-competitive. These bounds are shown to be tight.|
|Source Title:||Journal of Scheduling|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 11, 2018
WEB OF SCIENCETM
checked on Nov 26, 2018
checked on Oct 20, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.