Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Towards the 5/6-Density Conjecture of Pinwheel ...

Towards the 5/6-Density Conjecture of Pinwheel Scheduling

Sebastian Wild

June 16, 2022
Tweet

More Decks by Sebastian Wild

Other Decks in Research

Transcript

  1. 1/19 Towards the 5/6-Density Conjecture of Pinwheel Scheduling Ben Smith

    Leszek Gąsieniec and Sebastian Wild University of Liverpool January 2022
  2. 4/19 Introduction – the problem ▶ The Pinwheel Scheduling Problem1:

    ▶ 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)
  3. 4/19 Introduction – the problem ▶ The Pinwheel Scheduling Problem1:

    ▶ 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)
  4. 4/19 Introduction – the problem ▶ The Pinwheel Scheduling Problem1:

    ▶ 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)
  5. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  6. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  7. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  8. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  9. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  10. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  11. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = k i=1 1/ai ▶ [2, 3, M] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 . . . 3Chan and Chin, 1993 4Ding, 2020
  12. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = 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 3Chan and Chin, 1993 4Ding, 2020
  13. 5/19 Introduction – the 5/6 Density Conjecture ▶ Density d(A)

    = 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
  14. 6/19 Introduction – the literature not schedulable instances schedulable instances

    d > 1 d ≤ 5/6 d ≤ 0.75 d ≤ 0.7 d ≤ 0.66 5/6 Conj.
  15. 6/19 Introduction – the literature not schedulable instances schedulable instances

    d > 1 d ≤ 5/6 d ≤ 0.75 d ≤ 0.7 d ≤ 0.66 5/6 Conj. ≤ 12 tasks
  16. 8/19 Single instances ▶ Pinwheel as a directed graph ▶

    Example: [2 , 4 , 4] ▶ Schedulable iff the graph contains a directed cycle ▶ Slow, memory intensive ś so optimize the approach 0,0,0 0,1,1 1,0,1 1,1,0 0,2,2 1,0,2 0,3,3 1,0,3 1,3,0 0,1,3 1,2,0 0,3,1 0,1,2 0,2,3 0,2,1 0,3,2
  17. 8/19 Single instances – Optimisations 1. Naïve ▶ Generate the

    graph on demand as a DFS tree 0,0,0 0,1,1 1,0,1 1,1,0 0,2,2 1,0,2 0,3,3 1,0,3 1,3,0 0,1,3 1,2,0 0,3,1 0,1,2 0,2,3 0,2,1 0,3,2
  18. 8/19 Single instances – Optimisations 1. Naïve ▶ Generate the

    graph on demand as a DFS tree 2. Optimised ▶ Forbid immediate repetition 0,0,0 0,1,1 1,0,1 1,1,0 1,0,2 1,0,3 1,3,0 0,1,3 1,2,0 0,3,1 0,1,2 0,2,1
  19. 8/19 Single instances – Optimisations 1. Naïve ▶ Generate the

    graph on demand as a DFS tree 2. Optimised ▶ Forbid immediate repetition ▶ Exploit symmetry between duplicated frequencies ▶ Limit testing using minimum solution length 0,0,0 0,1,1 1,0,1 1,0,2 1,0,3 0,1,3 1,2,0 0,3,1 0,1,2
  20. 8/19 Single instances – Optimisations 1. Naïve ▶ Generate the

    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
  21. 9/19 Single instances – Tournament of Random Instances ▶ łhardnessž

    of input is challenging to predict ▶ x-axis is measured time to solve, not input size
  22. 11/19 Pareto surfaces Idea: Find set C of schedules that

    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 .
  23. 11/19 Pareto surfaces Idea: Find set C of schedules that

    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
  24. 12/19 Pareto surfaces up to k = 5 Instance Schedule

    (1) (1) (2 , 2) (1 , 2) (2 , 4 , 4) (1 , 2 , 1 , 3) (3 , 3 , 3) (1 , 2 , 3) (2 , 4 , 8 , 8) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4) (2 , 6 , 6 , 6) (1 , 2 , 1 , 3 , 1 , 4) (3 , 3 , 6 , 6) (1 , 2 , 3 , 1 , 2 , 4) (3 , 4 , 5 , 8) (1 , 2 , 4 , 1 , 3 , 2 , 1 , 3) (3 , 5 , 5 , 5) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 4) (4 , 4 , 4 , 4) (1 , 2 , 3 , 4) Instance Schedule (2 , 4 , 8 , 16 , 16) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 2 , 1 , 3 , 1 , 2 , 1 , 5) (2 , 4 , 12 , 12 , 12) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 2 , 1 , 5) (2 , 6 , 6 , 12 , 12) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 2 , 1 , 3 , 1 , 5) (2 , 6 , 8 , 10 , 16) (1 , 2 , 1 , 3 , 1 , 5 , 1 , 2 , 1 , 4 , 1 , 3 , 1 , 2 , 1 , 4) (2 , 6 , 10 , 10 , 10) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 2 , 1 , 5 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 5) (2 , 8 , 8 , 8 , 8) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 5) (3 , 3 , 6 , 12 , 12) (1 , 2 , 3 , 1 , 2 , 4 , 1 , 2 , 3 , 1 , 2 , 5) (3 , 3 , 9 , 9 , 9) (1 , 2 , 3 , 1 , 2 , 4 , 1 , 2 , 5) (3 , 4 , 5 , 14 , 14) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 1 , 2 , 5 , 1 , 3 , 2) (3 , 4 , 6 , 10 , 16) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 1 , 2 , 4 , 1 , 3 , 2 , 1 , 5) (3 , 4 , 6 , 11 , 11) (1 , 2 , 3 , 1 , 5 , 2 , 1 , 3 , 2 , 1 , 4) (3 , 4 , 8 , 8 , 8) (1 , 2 , 4 , 1 , 5 , 2 , 1 , 3) (3 , 5 , 5 , 9 , 9) (1 , 2 , 5 , 1 , 3 , 2 , 1 , 4 , 3) (3 , 5 , 6 , 7 , 12) (1 , 2 , 4 , 1 , 3 , 2 , 1 , 4 , 2 , 1 , 3 , 5) (3 , 5 , 7 , 7 , 9) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 5 , 3 , 1 , 2 , 4 , 1 , 3 , 2 , 1 , 5 , 4) (3 , 5 , 7 , 8 , 8) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 5 , 1 , 3 , 2 , 1 , 4 , 5) (3 , 6 , 6 , 6 , 6) (1 , 2 , 3 , 1 , 4 , 5) (4 , 4 , 4 , 8 , 8) (1 , 2 , 3 , 4 , 1 , 2 , 3 , 5) (4 , 4 , 5 , 7 , 12) (1 , 2 , 3 , 4 , 1 , 2 , 5 , 3 , 1 , 2 , 4 , 3) (4 , 4 , 6 , 6 , 6) (1 , 3 , 2 , 4 , 1 , 5 , 2 , 3 , 1 , 4 , 2 , 5) (4 , 5 , 5 , 6 , 10) (1 , 2 , 3 , 5 , 1 , 4 , 2 , 3 , 1 , 4) (4 , 5 , 5 , 7 , 7) (1 , 2 , 5 , 3 , 1 , 4 , 2 , 1 , 3 , 5 , 2 , 1 , 4 , 3) (5 , 5 , 5 , 5 , 5) (1 , 2 , 3 , 4 , 5)
  25. 12/19 Pareto surfaces up to k = 5 Instance Schedule

    (1) (1) (2 , 2) (1 , 2) (2 , 4 , 4) (1 , 2 , 1 , 3) (3 , 3 , 3) (1 , 2 , 3) (2 , 4 , 8 , 8) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4) (2 , 6 , 6 , 6) (1 , 2 , 1 , 3 , 1 , 4) (3 , 3 , 6 , 6) (1 , 2 , 3 , 1 , 2 , 4) (3 , 4 , 5 , 8) (1 , 2 , 4 , 1 , 3 , 2 , 1 , 3) (3 , 5 , 5 , 5) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 4) (4 , 4 , 4 , 4) (1 , 2 , 3 , 4) Instance Schedule (2 , 4 , 8 , 16 , 16) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 2 , 1 , 3 , 1 , 2 , 1 , 5) (2 , 4 , 12 , 12 , 12) (1 , 2 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 2 , 1 , 5) (2 , 6 , 6 , 12 , 12) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 2 , 1 , 3 , 1 , 5) (2 , 6 , 8 , 10 , 16) (1 , 2 , 1 , 3 , 1 , 5 , 1 , 2 , 1 , 4 , 1 , 3 , 1 , 2 , 1 , 4) (2 , 6 , 10 , 10 , 10) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 2 , 1 , 5 , 1 , 3 , 1 , 2 , 1 , 4 , 1 , 5) (2 , 8 , 8 , 8 , 8) (1 , 2 , 1 , 3 , 1 , 4 , 1 , 5) (3 , 3 , 6 , 12 , 12) (1 , 2 , 3 , 1 , 2 , 4 , 1 , 2 , 3 , 1 , 2 , 5) (3 , 3 , 9 , 9 , 9) (1 , 2 , 3 , 1 , 2 , 4 , 1 , 2 , 5) (3 , 4 , 5 , 14 , 14) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 1 , 2 , 5 , 1 , 3 , 2) (3 , 4 , 6 , 10 , 16) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 3 , 1 , 2 , 4 , 1 , 3 , 2 , 1 , 5) (3 , 4 , 6 , 11 , 11) (1 , 2 , 3 , 1 , 5 , 2 , 1 , 3 , 2 , 1 , 4) (3 , 4 , 8 , 8 , 8) (1 , 2 , 4 , 1 , 5 , 2 , 1 , 3) (3 , 5 , 5 , 9 , 9) (1 , 2 , 5 , 1 , 3 , 2 , 1 , 4 , 3) (3 , 5 , 6 , 7 , 12) (1 , 2 , 4 , 1 , 3 , 2 , 1 , 4 , 2 , 1 , 3 , 5) (3 , 5 , 7 , 7 , 9) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 5 , 3 , 1 , 2 , 4 , 1 , 3 , 2 , 1 , 5 , 4) (3 , 5 , 7 , 8 , 8) (1 , 2 , 3 , 1 , 4 , 2 , 1 , 5 , 1 , 3 , 2 , 1 , 4 , 5) (3 , 6 , 6 , 6 , 6) (1 , 2 , 3 , 1 , 4 , 5) (4 , 4 , 4 , 8 , 8) (1 , 2 , 3 , 4 , 1 , 2 , 3 , 5) (4 , 4 , 5 , 7 , 12) (1 , 2 , 3 , 4 , 1 , 2 , 5 , 3 , 1 , 2 , 4 , 3) (4 , 4 , 6 , 6 , 6) (1 , 3 , 2 , 4 , 1 , 5 , 2 , 3 , 1 , 4 , 2 , 5) (4 , 5 , 5 , 6 , 10) (1 , 2 , 3 , 5 , 1 , 4 , 2 , 3 , 1 , 4) (4 , 5 , 5 , 7 , 7) (1 , 2 , 5 , 3 , 1 , 4 , 2 , 1 , 3 , 5 , 2 , 1 , 4 , 3) (5 , 5 , 5 , 5 , 5) (1 , 2 , 3 , 4 , 5) Observation: All Pareto Surface members frequencies obey ai ≤ 2k−1.
  26. 14/19 5/6 Surface ▶ Find Ck,d≤5/6 i.e. Surface of instance

    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)
  27. 15/19 5/6 Surface – Unfolding ▶ Recall A = [3,

    4, 5, 8], and its schedule S = 1, 2, 4, 1, 3, 2, 1, 3 ▶ Use this to solve A′ = [3, 4, 5, 16, 16] by unfolding S ▶ S′ = 1, 2, 4, 1, 3, 2, 1, 3 1, 2, 5, 1, 3, 2, 1, 3 ▶ Application: Initializing the Pareto Surface ▶ 153 ± 2 times less oracle consultations at k = 8
  28. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    input: ▶ F1 = [5 , 6 , 7 , 9, 18, 19, 21], with k = 7 and d = 0 . 776
  29. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  30. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  31. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  32. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  33. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  34. 16/19 5/6 Surface – Folding ▶ Consider a challenging looking

    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
  35. 17/19 5/6 Surface – Kernelization ▶ Kernalization Conjecture: Any frequency

    ai ≥ 2k−1 can be reduced to a′ i = 2k−1 without affecting schedulability ▶ Application: Double down ś test both conjectures simultaneously
  36. 17/19 5/6 Surface – Kernelization ▶ Kernalization Conjecture: Any frequency

    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
  37. 18/19 Conclusion Results: ▶ The Pareto surface for k =

    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.
  38. 18/19 Conclusion Results: ▶ The Pareto surface for k =

    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