Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints

This research discusses hierarchy-based algorithms for minimizing makespan in scheduling problems with precedence and communication constraints. Various approximation techniques, open questions in scheduling theory, and QPTAS for different settings are explored, including the possibility of beating the 2-approximation factor in scheduling problems with NP-hard complexities.

• Scheduling Theory
• Approximation Algorithms
• Precedence Constraints
• Communication Constraints
• Makespan

wass_iya Follow

Uploaded on Oct 02, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints Janardhan Kulkarni Shi Li Jakub Tarnawski Minwei Ye Microsoft Research University at Buffalo 08.01.2020 SODA

2. Scheduling with precedence constraints Scheduling with precedence constraints ? jobs job ? has processing time (size) ?? ? identical machines partial order 2 4 1 3 makespan 1 2 What is the approximability of this problem? ?1 3 4

3. Graham (66): 2 Graham ( 66): 2- -approximation approximation Whenever a machine is idle, run any available job on it Greedy List Scheduling Makespan OPT + max length of a chain 2 OPT

4. Can one beat 2? Can one beat 2? Major open question in scheduling theory Lenstra, Rinnooy Kan ( 78): NP-hard to get 4 3 ? Svensson ( 10): UGC*-hard to get 2 ?, even for unit sizes (??= 1) rest of the talk What if ? = ?(1)? For many applications in practice this is OK.

5. What if What if ? = ?(1)? ? ? 2 3 NP-hard? (Garey, Johnson 79) has PTAS? (Schuurman, Woeginger 99) Levey, Rothvoss ( 16) in P unit sizes (??= 1) (Fujii, Kasami, Ninomiya 69) 7 4/3-apx 2 3?+1-apx (Lam, Sethi 77) (Gangal, Ranade 08) 1 ?-apx (Graham 66) 2 arbitrary sizes strongly NP-hard (Ullman 75)

6. QPTAS for ??= 1 Levey, Levey, Rothvoss Rothvoss ( 16): almost ( 16): almost- -QPTAS for Setting: unit sizes (??= 1) Define natural LP (its integrality gap is 2) Lift to r = (lg?)?(lg lg ?) levels of Lasserre hierarchy Rounding algorithm gives (1 + ?)-approximation Running time ??(?) A tantalizing question is whether a similar approach could give a (1 + )-approximation for the setting where Garg ( 17): r = (lg?)?(1) levels suffice (true QPTAS) the processing times are arbitrary

7. Arbitrary sizes Arbitrary sizes Three possible settings: Can Levey-Rothvoss be generalized? 1. Fully preemptive 2. Preemptive but non-migratory 3. Non-preemptive OPTs can be constant-factor away from each other

8. Arbitrary sizes Arbitrary sizes Three possible settings: Can Levey-Rothvoss be generalized? 1. Fully preemptive YES, this is simply equivalent to unit sizes: ??= 5

9. Arbitrary sizes Arbitrary sizes Three possible settings: Can Levey-Rothvoss be generalized? 1. Fully preemptive 2. Preemptive but non-migratory Our main result: YES (almost-QPTAS)

10. Arbitrary sizes Arbitrary sizes Three possible settings: Can Levey-Rothvoss be generalized? 1. Fully preemptive Our result: some evidence the lifted LP might be weak 2. Preemptive but non-migratory (even for 2 machines) 3. Non-preemptive

11. Communication delays Communication delays If ? ? are scheduled on different machines, need to wait ??,? ? ? ? ? ??,?

12. Communication delays Communication delays If ? ? are scheduled on different machines, need to wait ??,? Highly relevant to practice Bansal ( 17): Not understood at all. Almost completely open. No good LP/SDP relaxations known Hanen, Munier ( 01): 7/3-apx for unit sizes (??= 1), unit delays (??,? = 1) Our result: almost-QPTAS if ??,? ?(1) Arbitrary sizes (preemptive but non-migratory)

13. Our main result: almost-QPTAS for preemptive but non-migratory setting Levey-Rothvoss framework Outline of the Outline of the rest of talk rest of talk Challenges of arbitrary sizes Our new ideas

14. Graham (66): 2 Graham ( 66): 2- -approximation approximation Whenever a machine is idle, run any available job on it Makespan OPT + max length of a chain 2 OPT Crucial idea: get (1 + ?)-apx if longest chain ? ??? Use LP hierarchy to cut long chains

15. Hierarch Hierarchy as black box y as black box We have ???= 1 meaning: job ? should be scheduled at time ?. Conditioning operation: Given solution ? of level ? with ???> 0, can produce ? of level ? 1 with ? ??= 1. Can fix an integral timeslot ? for job ?by paying 1 level .

16. Using ? and conditioning, partition: top jobs with short chains bottom jobs with short supports Levey Levey- -Rothvoss framework Rothvoss framework top jobs Recursively schedule bottom jobs Algorithm to add top jobs to schedule bottom jobs Properties of constraints: bottom-to-bottom: recursive / automatic top-to-bottom: ``loose top-to-top: short chains ?2 ?3 ?1 ? 0 EDF (Earliest Deadline First) scheduling does the trick

17. Using ? and conditioning, partition: top jobs with short chains bottom jobs with short supports Challenges of arbitrary sizes Challenges of arbitrary sizes Why not just do this? small-jobs big-job Imagine ??= ?. Not short chain, not short support; so need to split among bottom intervals But then, no control: small-jobs could go to different machines

18. Our ideas Our ideas New machine-indexed LP ????= small-job ? scheduled at time ? on machine ? no-migration constraints conditioning on one small-job fixes ? for all sibling small-jobs Special treatment of conditioned jobs: new splitting operation they are always pushed down to bottom of recursion, and there scheduled solely using LP guarantees correct machine assignment ? = 3 ? = 3 ? = 3 ? = 8 ? = 3 ? = 9 ? = 3 ? = 5

19. Adding top jobs to schedule Adding top jobs to schedule ?2 ?3 ?1 ? 0 sibling small-jobs? Levey-Rothvoss (unit sizes): EDF (Earliest Deadline First) scheduling does the trick New algorithm to schedule top jobs: treat big-jobs together to choose job: EDF (Earliest Deadline First) to choose machine: ECT (Earliest Completion Time) But it creates a migratory schedule!

20. Summary Summary + a few words on our hardness result

21. Our results (1/3) Our results (1/3) Theorem 1. For any ? > 0,? 1, there is an algorithm for makespan scheduling on ? identical machines with precedence constraints of arbitrary-sized jobs with preemption but no migration that: runs in time ?(lg ?)?(lg lg ?) gives a (1 + ?)-approximation

22. Our results (2/3) Our results (2/3) Theorem 2. For any ? > 0,? 1, ? 0, there is an algorithm for makespan scheduling on ? identical machines with precedence constraints and communication delays ??,? ? of arbitrary-sized jobs with preemption but no migration that: runs in time ?(lg ?)?(lg lg ?) gives a (1 + ?)-approximation

23. Our results (3/3): evidence of hardness Our results (3/3): evidence of hardness? ? A special case of: A deadline scheduling problem 2 machines, arbitrary sizes, no preemption Theorem 3. A natural LP lifted to ?(????) levels is weak Via this reduction, can t tell if: Makespan < 1 + ? ? Makespan > 1.1? i.e. this doesn t give a PTAS We can t reason about the LP for makespan but we think our hard instance is the right one

24. Future work Future work

25. Future work Future work Are ??,?(1) levels enough? For unit sizes: some experts think ? is enough. Works for ? = 2 Non-preemptive setting: hardness? Are lifted LPs weak on our candidate hard instance? Communication delays: Unbounded ??,? : no nontrivial approximation known Unit sizes: 100 machines: NP-hard? 3 machines: PTAS? Thank you!