### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Centre for Telematics and Information Technology (CTIT) |

Number of pages | 14 |

Publication status | Published - Jul 2012 |

### Publication series

Name | CTIT Technical Report Series |
---|---|

Publisher | University 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

*Decentralized Throughput Scheduling*. (CTIT Technical Report Series; No. TR-CTIT-12-18). Enschede: Centre for Telematics and Information Technology (CTIT).

}

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

Research output: Book/Report › Report › Professional

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 -