Competitive on-line scheduling with Level of Service

Ee Chien Chang, Chee Yap

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)251-267
Number of pages17
JournalJournal of Scheduling
Volume6
Issue number3
DOIs
StatePublished - May 2003

Keywords

  • Competitive analysis
  • Level of service
  • On-line scheduling

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Competitive on-line scheduling with Level of Service'. Together they form a unique fingerprint.

  • Cite this