Search Results

Documents authored by Uetz, Marc

Document
DOI: 10.4230/LIPIcs.STACS.2014.639
Stochastic Scheduling on Unrelated Machines

Authors: Martin Skutella, Maxim Sviridenko, and Marc Uetz

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the sizes of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. Here, the processing time of job j on machine i is governed by random variable P_{ij} , and its realization becomes known only upon job completion. With w_j being the given weight of job j, we study the objective to minimize the expected total weighted completion time E[Sum w_j.C_j] , where C_j is the completion time of job j. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+D)/2+e. Here, e>0 is arbitrarily small, and D is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates r_{ij}, our bound is (2+D)+e. We also show that the dependence of the performance guarantees on D is tight. Via D=0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.
Cite as

Martin Skutella, Maxim Sviridenko, and Marc Uetz. Stochastic Scheduling on Unrelated Machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 639-650, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{skutella_et_al:LIPIcs.STACS.2014.639,
  author =	{Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
  title =	{{Stochastic Scheduling on Unrelated Machines}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{639--650},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.639},
  URN =		{urn:nbn:de:0030-drops-44946},
  doi =		{10.4230/LIPIcs.STACS.2014.639},
  annote =	{Keywords: Stochastic Scheduling, Unrelated Machines, Approximation Algorithm}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.7
Optimal Mechanisms for Scheduling

Authors: Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
We study the design of optimal mechanisms in a setting where a service provider needs to schedule a set of non-preemptive jobs, one job at a time. Jobs need to be compensated for waiting, and waiting cost is private information. In this setting, an optimal mechanism is one that induces jobs to report truthfully their waiting cost, while minimizing the total expected compensation cost of the service provider. Here, truthful refers to Bayes-Nash implementability, and assumes that private information is independently drawn from known distributions. We derive closed formulae for the optimal mechanism, and show that it is a modification of Smith’s ratio rule. We also show that it can be implemented in dominant strategies. Our analysis relies on a graph-theoretic interpretation of the incentive compatibility constraints. It parallels the analysis known for auctions with single parameter agents, yet it exhibits some subtle differences. We also consider the multi-dimensional case where also the service times of jobs are private information. We show that for this problem the optimal mechanism generally does not satisfy an independence condition known as IIA, and thus known approaches are doomed to fail.
Cite as

Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz. Optimal Mechanisms for Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.10071.7,
  author =	{Heydenreich, Birgit and Mishra, Debasis and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Optimal Mechanisms for Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.7},
  URN =		{urn:nbn:de:0030-drops-25401},
  doi =		{10.4230/DagSemProc.10071.7},
  annote =	{Keywords: Optimal Mechanism Design, Scheduling, Job Agents, Smith's Rule}
}
Document
DOI: 10.4230/DagSemProc.07271.11
On Revenue Equivalence in Truthful Mechanisms

Authors: Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)

Abstract
The property of an allocation rule to be implementable in dominant strategies by a unique payment scheme is called revenue equivalence. In this paper we give a characterization of revenue equivalence based on a graph theoretic interpretation of the incentive compatibility constraints. The characterization holds for any (possibly infinite) outcome space and many of the known results about revenue equivalence are immediate consequences.
Cite as

Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra. On Revenue Equivalence in Truthful Mechanisms. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.07271.11,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc and Vohra, Rakesh},
  title =	{{On Revenue Equivalence in Truthful Mechanisms}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.11},
  URN =		{urn:nbn:de:0030-drops-11581},
  doi =		{10.4230/DagSemProc.07271.11},
  annote =	{Keywords: Mechanism Design, Revenue Equivalence, Graph Theory}
}
Document
DOI: 10.4230/DagSemProc.06461.7
Decentralization and Mechanism Design for Online Machine Scheduling

Authors: Birgit Heydenreich, Rudolf Müller, and Marc Uetz

Published in: Dagstuhl Seminar Proceedings, Volume 6461, Negotiation and Market Engineering (2007)

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 that the data of each job, 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 problem from the perspective of algorithmic mechanism design. We introduce the concept of a myopic best response equilibrium, a concept weaker than the dominant strategy equilibrium, but appropriate for online problems. We present a polynomial time, online scheduling mechanism that, assuming rational behavior of jobs, results in an equilibrium schedule that is 3.281-competitive. The mechanism deploys an online payment scheme that induces rational jobs to truthfully report their private data. We also show that the underlying local scheduling policy cannot be extended to a mechanism where truthful reports constitute a dominant strategy equilibrium.
Cite as

Birgit Heydenreich, Rudolf Müller, and Marc Uetz. Decentralization and Mechanism Design for Online Machine Scheduling. In Negotiation and Market Engineering. Dagstuhl Seminar Proceedings, Volume 6461, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.06461.7,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Decentralization and Mechanism Design for Online Machine Scheduling}},
  booktitle =	{Negotiation and Market Engineering},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6461},
  editor =	{Nick Jennings and Gregory Kersten and Axel Ockenfels and Christof Weinhardt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06461.7},
  URN =		{urn:nbn:de:0030-drops-10030},
  doi =		{10.4230/DagSemProc.06461.7},
  annote =	{Keywords: Scheduling, mechanism design, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.05031.15
Models and Algorithms for Stochastic Online Scheduling

Authors: Nicole Megow, Marc Uetz, and Tjark Vredeveld

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
We introduce a model for non-preemptive scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to the classical stochastic scheduling models, we assume that jobs arrive online over time, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic parallel machine scheduling. For processing times that follow NBUE distributions, we improve upon previously best known performance bounds, even though we consider a more general setting.
Cite as

Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and Algorithms for Stochastic Online Scheduling. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{megow_et_al:DagSemProc.05031.15,
  author =	{Megow, Nicole and Uetz, Marc and Vredeveld, Tjark},
  title =	{{Models and Algorithms for Stochastic Online Scheduling}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.15},
  URN =		{urn:nbn:de:0030-drops-1106},
  doi =		{10.4230/DagSemProc.05031.15},
  annote =	{Keywords: stochastic scheduling , online optimization , weighted completion time}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact