Pinwheel scheduling with three distinct numbers

Shun Shii Lin, Kwei Jay Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (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.

Original languageEnglish
Title of host publicationProceedings - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
Number of pages6
Publication statusPublished - 1994
Event6th Euromicro Workshop on Real-Time Systems, ECRTS 1994 - Vaesteraas, Sweden
Duration: 1994 Jun 151994 Jun 17

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070


Other6th Euromicro Workshop on Real-Time Systems, ECRTS 1994

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'Pinwheel scheduling with three distinct numbers'. Together they form a unique fingerprint.

Cite this