Show simple item record

dc.contributor.authorTelelis, Orestis
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorGourvès, Laurent
dc.date.accessioned2010-06-29T16:13:16Z
dc.date.available2010-06-29T16:13:16Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4488
dc.language.isoenen
dc.subjectSchedulingen
dc.subject.ddc003en
dc.titleSelfish scheduling with setup timesen
dc.typeCommunication / Conférence
dc.description.abstractenWe study multiprocessor scheduling games with setup times on identical machines. Given a set of scheduling policies (coordination mechanism) on the machines, each out of n players chooses a machine to assign his owned job to, so as to minimize his individual completion time. Each job has a processing length and is of a certain type. Same-type jobs incur a setup overhead to the machine they are assigned to. We study the Price of Anarchy with respect to the makespan of stable assignments, that are pure Nash or strong equilibria for the underlying strategic game. We study in detail the performance of a well established preemptive scheduling mechanism. In an effort to improve over its performance, we introduce a class of mechanisms with certain properties, for which we examine existence of pure Nash and strong equilibria. We identify their performance limitations, and analyze an optimum mechanism out of this class. Finally, we point out several interesting open problems.en
dc.identifier.citationpages292-303en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5929
dc.relation.ispartoftitleInternet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedingsen
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2009
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-10841-9en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-10840-2en
dc.relation.conftitle5th International Workshop, WINE 2009en
dc.relation.confdate2009-12
dc.relation.confcityRomeen
dc.relation.confcountryItalieen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-10841-9_27


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record