Template-type: ReDif-Paper 1.0
Author-Name: Heydenreich Birgit 
Author-Name: Müller, Rudolf 
Author-Name: Uetz, Marc 
Author-workplace-name: METEOR
Title: Decentralization and Mechanism Design for Online Machine Scheduling
Abstract: We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time  from a new perspective: We assume a strategic setting, where the data of each job j, namely its release date r(j) , its processing time p(j) and its weight w(j) is only known to the job itself, but not to the system. Furthermore, we assume a decentralized setting, where jobs choose the machine on which they want to be processed themselves. We study this setting from the perspective of algorithmic mechanism design and present a polynomial time decentralized online scheduling mechanism that induces rational jobs to select their machine in such a way that the resulting schedule is 3.281-competitive. The mechanism deploys an online payment scheme that induces rational jobs to truthfully report about their private data: with respect to release dates and processing times, truthfully reporting is a dominant strategy equilibrium, whereas truthfully reporting the weights is a myopic best response equilibrium. We also show that the local  scheduling policy used in the mechanism cannot be extended to a mechanism where truthful reports with respect to weights constitute a dominant strategy equilibrium.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2006
Number: 007
File-URL: http://edocs.ub.unimaas.nl/loader/file.asp?id=1150
File-Format: application/pdf
File-Size: 248162
Handle: RePEc:unm:umamet:2006007