Pinwheel Scheduling: Achievable Densities

Pinwheel Scheduling: Achievable Densities

0.00 Avg rating0 Votes
Article ID: iaor20121114
Volume: 34
Issue: 1
Start Page Number: 14
End Page Number: 38
Publication Date: Sep 2002
Journal: Algorithmica
Authors: ,
Keywords: linear algebra
Abstract:

A pinwheel schedule for a vector v= (v1, v2, …, vn ) of positive integers 2 ≤ v1 ≤ v2 ≤ ·s ≤ vn is an infinite symbol sequence {Sj: j ∈ Z} with each symbol drawn from [n] = {1,2, …, n } such that each i ∈ [n] occurs at least once in every vi consecutive terms (Sj+1, Sj+2, …, Sj+vi ) . The density of v is d(v) = 1/v1 + 1/v2 + ·s + 1/vn . If v has a pinwheel schedule, it is schedulable . It is known that v(2,3,m) with m ≥ 6 and density d(v) = 5/6 + 1/m is unschedulable, and Chan and Chin [2] conjecture that every v with d(v) ≤ 5/6 is schedulable. They prove also that every v with d(v) ≤ 7/10 is schedulable.We show that every v with d(v) ≤ 3/4 is schedulable, and that every v with v 1 =2 and d(v) ≤ 5/6 is schedulable. The paper also considers the mpinwheel scheduling problem for v , where each i ∈ [n] is to occur at least m times in every mv i consecutive terms (S j+1 , …, S j+mvi ) , and shows that there are unschedulable vectors with d(v) =1- 1/[(m+1)(m+2)] + ϵ for any ϵ > 0 .

Reviews

Required fields are marked *. Your email address will not be published.