Competitive On-Line Scheduling with Level of Service

Ee-Chien Chang, Chee-Keng YapJ. Sched 2003 · DOI · OpenReview

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.
BibTeX
@article{chang2003competitive,
  author = {Ee-Chien Chang and Chee-Keng Yap},
  title = {{Competitive On-Line Scheduling with Level of Service}},
  journal = {J. Sched.},
  year = {2003},
  doi = {10.1023/a:1022904408360},
}

Loading related content...

Figure