Explore a 20-minute IEEE conference talk on scheduling precedence-constrained jobs on related machines with communication delay. Learn about duplication techniques, heterogeneous processing, and the challenges of delay constraints. Discover the makespan algorithm, integrality gap, and LP relaxation approaches. Gain insights into the main results, techniques, and open problems in this field of study presented by researchers from Northeastern University, Google, and Northwestern University.
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Overview
Syllabus
Intro
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
Precedence-Constrained Scheduling on
Duplication A job is duplicated it is cute on multiple machines Duplication can be helpful in prence of communication delay
Motivation: Heterogenous Processing
Prior & Related Work
Central Question
Makespan Algorithm
Integrality Gap
Bounding the Duplication Advantage
Challenges: Delay Constraints
LP Relaxation
Algorithm Overview
Iterative Scheduling
Lower Bound
Main Result & Techniques
Open Problems
Taught by
IEEE FOCS: Foundations of Computer Science
