Nonpreemptive Coordination Mechanisms for Identical Machines

We focus on the problem of scheduling n weighted selfish tasks on m identical parallel machines and we study the performance of nonpreemptive coordination mechanisms. A nonpreemptive coordination mechanism consists of  m local scheduling policies that decide the processing order of the tasks on each...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2013-10, Vol.53 (3), p.424-440
Main Author: Kollias, Konstantinos
Format: Article
Language:English
Subjects:
Analysis
Communication
Computation
Computer Science
Costs
Delay
Equilibrium
Game theory
Interruption
Job shops
Lower bounds
Mathematical models
Policies
Processing speed
Scheduling
Studies
Tasks
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We focus on the problem of scheduling n weighted selfish tasks on m identical parallel machines and we study the performance of nonpreemptive coordination mechanisms. A nonpreemptive coordination mechanism consists of  m local scheduling policies that decide the processing order of the tasks on each machine without delays or interruptions. We discuss the existence of Nash equilibria for this setting and show that it is not a guaranteed property of all nonpreemptive coordination mechanisms. Next, we focus on the wider class of randomized Nash equilibria and prove lower bounds on the price of anarchy. Our lower bounds are presented in comparison to the currently best known coordination mechanism (which uses delays) and lead to the conclusion that preemption or delays are required in order to improve on the currently best known solution.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-012-9429-9