Pinwheel scheduling with three distinct numbers

Shun-Shii Lin, Kwei Jay Lin

研究成果: 書貢獻/報告類型會議論文篇章

4 引文 斯高帕斯(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). We limit ourselves to instances composed of three distinct integers. Currently, the best scheduler [5] can schedule such instances with a density less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is proposed which improves the 0.77 result to a new 5/6 ≈ 0.83 density threshold. This scheduler has achieved the exact theoretical bound of this problem.

原文英語
主出版物標題Proceedings - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
頁面174-179
頁數6
DOIs
出版狀態已發佈 - 1994 十二月 1
事件6th Euromicro Workshop on Real-Time Systems, ECRTS 1994 - Vaesteraas, 瑞典
持續時間: 1994 六月 151994 六月 17

出版系列

名字Proceedings - Euromicro Conference on Real-Time Systems
ISSN(列印)1068-3070

其他

其他6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
國家/地區瑞典
城市Vaesteraas
期間1994/06/151994/06/17

ASJC Scopus subject areas

  • 軟體
  • 硬體和架構

指紋

深入研究「Pinwheel scheduling with three distinct numbers」主題。共同形成了獨特的指紋。

引用此