Decentralized Throughput Scheduling

Jasper de Jong, Marc Jochen Uetz, Andreas Wombacher

Research output: Book/ReportReportProfessional

63 Downloads (Pure)

Abstract

Motivated by the organization of online service systems, we study models for throughput scheduling in a decentralized setting. In throughput scheduling, we have a set of jobs j with values w(j), processing times p(j), and release dates r(j) and deadlines and d(j), to be processed non-preemptively on a set of unrelated machines. The goal is to maximize the total value of jobs scheduled within their time window [r(j),d(j)]. While several approximation algorithms with different performance guarantees exist for this and related models, we are interested in the situation where subsets of servers are governed by selfish players. We give a universal result that bounds the price of decentralization, in the sense that any local a-approximation algorithms yield equilibria that are at most a factor (a+1) away from the global optimum, and this bound is tight. For models with identical machines, we improve this bound to approximately (a+1/2). We also address some variations of the problem.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages14
Publication statusPublished - Jul 2012

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
No.TR-CTIT-12-18
ISSN (Print)1381-3625

Keywords

  • Price of Anarchy
  • Throughput Scheduling
  • Decentralization
  • IR-80711
  • METIS-289646
  • DMMP-DSS: Mechanisms for Decentralized Service Systems
  • EWI-22000

Cite this