▶ Given k tasks (each with frequency ai ∈ N) Is there a perpetual schedule for a (single) agent who can perform one task per day such that every section of length ai contains at least one instance of task i? 1Holte et.al., 1989 2Jacobs and Longo, 2014(arxiv)
▶ Given k tasks (each with frequency ai ∈ N) Is there a perpetual schedule for a (single) agent who can perform one task per day such that every section of length ai contains at least one instance of task i? ▶ Example: ▶ A = [3 , 4 , 5 , 8] k=4 Task 1 2 3 4 Frequency 3 4 5 8 ▶ S = 1 , 2 , 4 , 1 , 3 , 2 , 1 , 3 3 4 8 3 5 4 3 5 1Holte et.al., 1989 2Jacobs and Longo, 2014(arxiv)
▶ Given k tasks (each with frequency ai ∈ N) Is there a perpetual schedule for a (single) agent who can perform one task per day such that every section of length ai contains at least one instance of task i? ▶ Example: ▶ A = [3 , 4 , 5 , 8] k=4 Task 1 2 3 4 Frequency 3 4 5 8 ▶ S = 1 , 2 , 4 , 1 , 3 , 2 , 1 , 3 3 4 8 3 5 4 3 5 ▶ NP Hard2 1Holte et.al., 1989 2Jacobs and Longo, 2014(arxiv)
= k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . ▶ 5/6 Density Conjecture: All Pinwheel scheduling instances where d ≤ 5/6 are schedulable.3 ▶ Proven for k ≤ 5 tasks.4 ▶ Contribution: We prove this for k ≤ 12 3Chan and Chin, 1993 4Ding, 2020
graph on demand as a DFS tree 2. Optimised ▶ Forbid immediate repetition ▶ Exploit symmetry between duplicated frequencies ▶ Limit testing using minimum solution length 3. Foresight ▶ Urgency: time until the next constraint violation ▶ Forcing: finding the composition of the next few moves ▶ Dooming: finding that a node must lead to constraint violations ▶ Consider a sample state from [3, 4, 5, 8] 1,2,4,0 ▶ Switch to Urgency 1,1,0,7 ▶ u2 = 0 − → u2 is forced ▶ 3 elements with ui ≤ 1 − → this state is doomed 1,1,0,7
solves entire family of instances. i.e. an instance is schedulable ⇐⇒ a schedule from C solves it Theorem: Any set of schedulable PWS instances with k tasks can be solved by a őnite set of schedules Ck .
solves entire family of instances. i.e. an instance is schedulable ⇐⇒ a schedule from C solves it Theorem: Any set of schedulable PWS instances with k tasks can be solved by a őnite set of schedules Ck . Proof yields an algorithm to őnd Ck by computing the Pareto Trie: 1 2 2,2-3 2,4 2,4,4-7 2,4,8 2,4,8,8 2,5 2,6 2,6,6 2,6,6,6 3 3,3 3,3,3-5 3,3,6 3,3,6,6 3,4 3,4,4 3,4,5 3,4,5,8 3,4,6 3,4,7 3,4,6,7 3,4,7,7 3,5 3,5,5 3,5,5,5 4 4,4 4,4,4 4,4,4,4 2,5,5-7 2,5,8,8 2,5,8 3,4,6,6 3,4,5,5-7 ⇝ every instance with k = 4 is either: ▶ written in the trie ▶ an unschedulable child of a blue node ▶ shares a schedule with a green node
with k tasks and density ≤ 5/6 ▶ Optimize using the density gap & the belief that all instances are schedulable ▶ “Unfolding” ▶ “Folding” ▶ Kernelization (also some data structures)
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001 ▶ Observation 1: F3 is trivially schedulable by S = 0, 1, 2, 3, 4 ▶ Observation 2: this can make unschedulable problems from schedulable inputs
input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776 ▶ Combine the last several elements to make problems whose unfolded schedules would solve F1 : k d F2 = [5, 6, 7, 9, 9, 18] 6 0.787 F3 = [5, 6, 6, 7, 9] 5 0.787 F4 = [2, 5, 6, 7] 4 1.001 ▶ Observation 1: F3 is trivially schedulable by S = 0, 1, 2, 3, 4 ▶ Observation 2: this can make unschedulable problems from schedulable inputs ▶ Application: Attempt multiple foldings in parallel
ai ≥ 2k−1 can be reduced to a′ i = 2k−1 without affecting schedulability ▶ Application: Double down ś test both conjectures simultaneously ▶ Achievement: Kernalisation Conjecture true for k ≤ 12 and d ≤ 5/6 ▶ Achievement: 5/6 Conjecture true for k ≤ 12
5. ▶ Proof of the 5/6 Conjecture for k ≤ 12. ▶ The Kernalization Conjecture, which holds for k ≤ 5 and k ≤ 12, d ≤ 5/6. ▶ A fast Pinwheel Scheduling oracle, available online.
5. ▶ Proof of the 5/6 Conjecture for k ≤ 12. ▶ The Kernalization Conjecture, which holds for k ≤ 5 and k ≤ 12, d ≤ 5/6. ▶ A fast Pinwheel Scheduling oracle, available online. Open problems: ▶ Implications for Bamboo Garden Trimming ▶ The Kernalization Conjecture ▶ The 5/6 Density Conjecture
sebawild
takase
trafficbrain
chemical_tree
hargon24
agiats
hiromu1996
kentosasaki
ryou0634
udonda
ynakano
litalicolab
daimoriwaki
ddemaree
swwweet
sferik
brianwarren
jmmastey
zakiyama
tanoku
tammyeverts
gr2m
lauravandoore
keithpitt
bluesmoon
