Cost-oblivious reallocation for scheduling and planning

Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule. This paper gives a reallocating scheduler for the problem of assigning jobs to p (identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a lengthw job of O(f(w) · log log Δ), where Δ is the length of the longest job and f() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized by f(), yet it achieves this bound for any subadditive f(). Whenever f() is strongly subadditive, the reallocation cost becomes O(f(w)). To realize a reallocating scheduler with low reallocation cost, we design a k-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted to k "cursors" in the structure. The data structure achieves an amortized cost of O(log k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted to k < n cursors, beats the lower bound of Ω(log n) for general sparse tables.

Original languageEnglish (US)
Title of host publicationSPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages143-154
Number of pages12
ISBN (Electronic)9781450335881
DOIs
StatePublished - Jun 13 2015
Event27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 - Portland, United States
Duration: Jun 13 2015Jun 15 2015

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Volume2015-June

Other

Other27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
Country/TerritoryUnited States
CityPortland
Period6/13/156/15/15

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Cost-oblivious problems
  • Reallocation
  • Resource allocation

Fingerprint

Dive into the research topics of 'Cost-oblivious reallocation for scheduling and planning'. Together they form a unique fingerprint.

Cite this