A pinwheel scheduler for three distinct numbers with a tight schedulability bound

Shun Shii Lin, Kwei Jay Lin

研究成果: 雜誌貢獻期刊論文同行評審

19 引文 斯高帕斯(Scopus)

摘要

Given a multiset of positive integers A = {a1, a2, . . . , an}, the pinwheel problem is to find an infinite sequence over {1, 2, . . . , n} such that there is at least one symbol i within any subsequence of length ai. The density of A is defined as ρ (A) = ∑i=1n(1/ai). In this paper we limit ourselves to instances composed of three distinct integers. The best scheduler [5] published previously can schedule all instances with a density of less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is presented in this paper which improves the 0.77 result to a new 5/6 ≈ 0.83 density threshold. This scheduler has achieved the tight schedulability bound of this problem.

原文英語
頁(從 - 到)411-426
頁數16
期刊Algorithmica (New York)
19
發行號4
DOIs
出版狀態已發佈 - 1997 一月 1

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

指紋 深入研究「A pinwheel scheduler for three distinct numbers with a tight schedulability bound」主題。共同形成了獨特的指紋。

引用此