Decentralized Throughput Scheduling

Jasper de Jong, Marc Jochen Uetz, Andreas Wombacher

Research output: Book/ReportReportProfessional

41 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

de Jong, J., Uetz, M. J., & Wombacher, A. (2012). Decentralized Throughput Scheduling. (CTIT Technical Report Series; No. TR-CTIT-12-18). Enschede: Centre for Telematics and Information Technology (CTIT).
de Jong, Jasper ; Uetz, Marc Jochen ; Wombacher, Andreas. / Decentralized Throughput Scheduling. Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 14 p. (CTIT Technical Report Series; TR-CTIT-12-18).
@book{a5a7fc7f3a024e4a8ac315f427ab045e,
title = "Decentralized Throughput Scheduling",
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.",
keywords = "Price of Anarchy, Throughput Scheduling, Decentralization, IR-80711, METIS-289646, DMMP-DSS: Mechanisms for Decentralized Service Systems, EWI-22000",
author = "{de Jong}, Jasper and Uetz, {Marc Jochen} and Andreas Wombacher",
year = "2012",
month = "7",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-12-18",
address = "Netherlands",

}

de Jong, J, Uetz, MJ & Wombacher, A 2012, Decentralized Throughput Scheduling. CTIT Technical Report Series, no. TR-CTIT-12-18, Centre for Telematics and Information Technology (CTIT), Enschede.

Decentralized Throughput Scheduling. / de Jong, Jasper; Uetz, Marc Jochen; Wombacher, Andreas.

Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 14 p. (CTIT Technical Report Series; No. TR-CTIT-12-18).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Decentralized Throughput Scheduling

AU - de Jong, Jasper

AU - Uetz, Marc Jochen

AU - Wombacher, Andreas

PY - 2012/7

Y1 - 2012/7

N2 - 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.

AB - 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.

KW - Price of Anarchy

KW - Throughput Scheduling

KW - Decentralization

KW - IR-80711

KW - METIS-289646

KW - DMMP-DSS: Mechanisms for Decentralized Service Systems

KW - EWI-22000

M3 - Report

T3 - CTIT Technical Report Series

BT - Decentralized Throughput Scheduling

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

de Jong J, Uetz MJ, Wombacher A. Decentralized Throughput Scheduling. Enschede: Centre for Telematics and Information Technology (CTIT), 2012. 14 p. (CTIT Technical Report Series; TR-CTIT-12-18).