Competitive Algorithms from Competitive Equilibria
Abstract
We introduce and study a general scheduling problem that we term the Polytope Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates assigned by the scheduler to the jobs are subject to arbitrary packing constraints. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 11, 2017
- Source ID
- 10.1145/3136754
Entities
People
- Janardhan Kulkarni
- Kamesh Munagala
- Sungjin Im
Organizations
- Army Research Office
- Cisco
- Duke University
- Microsoft Research
- National Science Foundation
- University of California