Online scheduling of unit jobs with bounded importance ratio

Stanley P.Y. Fung, Francis Y.L. Chin, Hong Shen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. In this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight.

Original languageEnglish
Pages (from-to)581-598
Number of pages18
JournalInternational Journal of Foundations of Computer Science
Issue number3
Publication statusPublished - Jun 2005
Externally publishedYes


  • Competitive analysis
  • Importance ratio
  • Online scheduling
  • Quality of service


Dive into the research topics of 'Online scheduling of unit jobs with bounded importance ratio'. Together they form a unique fingerprint.

Cite this