Name
Abstract | ||
|---|---|---|
Abstract. A pinwheel schedule for a vector v= (v
1
, v
2
, . . ., v
n
) of positive integers 2 ≤ v
1
≤ v
2
≤ ⋅s ≤ v
n
is an infinite symbol sequence {S
j
: j ∈ Z } with each symbol drawn from [n] = {1,2, . . ., n } such that each i ∈ [n] occurs at least once in every v
i
consecutive terms (S
j+1
, S
j+2
, . ., S
j+vi
) . The density of v is d(v) = 1/v
1
+ 1/v
2
+ ⋅s + 1/v
n
. 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 m -pinwheel 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 .
|
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s00453-002-0938-9 | Algorithmica |
Keywords | Field | DocType |
Key words. Pinwheel,Scheduling,Density guarantee,Packing. | Integer,Pinwheel,Discrete mathematics,Combinatorics,Three dimensional model,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
34 | 1 | 0178-4617 |
Citations | PageRank | References |
9 | 0.56 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter C. Fishburn | 1 | 740 | 136.75 |
| J. C. Lagarias | 2 | 563 | 235.61 |