Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints

Journal Article (Journal Article)

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. We show a surprising result—there is a single algorithm that is O(1) competitive for all PSP instances when the objective is total completion time, and O(1) competitive for a large sub-class of PSP instances when the objective is total flow time. This algorithm simply uses the well-known Proportional Fairness (PF) algorithm to perform allocations each time instant. Though PF has been extensively studied in the context of maximizing fairness in resource allocation, we present the first analysis in adversarial and general settings for optimizing job latency. Further, PF is non-clairvoyant, meaning that the algorithm doesn’t need to know jobs sizes until their completion. We establish our positive results by making novel connections with Economics, in particular, the notions of market clearing, Gross Substitutes, and Eisenberg-Gale markets. We complement these positive results with a negative result: We show that for the total flow time objective, any non-clairvoyant algorithm for general PSP has a strong lower bound on the competitive ratio unless given a poly-logarithmic speed augmentation. This motivates the need to consider sub-classes of PSP when studying flow time. The sub-class for which we obtain positive results not only captures several well-studied models, such as scheduling with speedup curves and related machine scheduling, but also captures as special cases hitherto unstudied scheduling problems, such as single source flow routing, routing multicast (video-on-demand) trees, and resource allocation with substitute resources.

Full Text

Duke Authors

Cited Authors

  • Sungjin, IM; Munagala, K; Kulkarni, J

Published Date

  • December 1, 2017

Published In

Volume / Issue

  • 65 / 1

Electronic International Standard Serial Number (EISSN)

  • 1557-735X

International Standard Serial Number (ISSN)

  • 0004-5411

Digital Object Identifier (DOI)

  • 10.1145/3136754

Citation Source

  • Scopus