Search Results

Documents authored by Schwiegelshohn, Uwe

Document
DOI: 10.4230/LIPIcs.ESA.2016.75
The Power of Migration for Online Slack Scheduling

Authors: Chris Schwiegelshohn and Uwe Schwiegelshohn

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We investigate the power of migration in online scheduling for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. Once we decide to accept a job, we have to complete it before its deadline d that satisfies d >= (1+epsilon)p + r, where p is the processing time, r the submission time and the slack epsilon > 0 a system parameter. Typically, the hard case arises for small slack epsilon << 1, i.e. for near-tight deadlines. Without migration, a greedy acceptance policy is known to be an optimal deterministic online algorithm with a competitive factor of (1+epsilon)/epsilon (DasGupta and Palis, APPROX 2000). Our first contribution is to show that migrations do not improve the competitive ratio of the greedy acceptance policy, i.e. the competitive ratio remains (1+epsilon)/epsilon for any number of machines. Our main contribution is a deterministic online algorithm with almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound of (1+epsilon)/epsilon of the greedy acceptance policy. The competitive ratio improves with an increasing number of machines. It approaches (1+epsilon) ln((1+epsilon)/epsilon) as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small epsilon. Moreover, we show a matching lower bound on the competitive ratio for deterministic algorithms on any number of machines.
Cite as

Chris Schwiegelshohn and Uwe Schwiegelshohn. The Power of Migration for Online Slack Scheduling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{schwiegelshohn_et_al:LIPIcs.ESA.2016.75,
  author =	{Schwiegelshohn, Chris and Schwiegelshohn, Uwe},
  title =	{{The Power of Migration for Online Slack Scheduling}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{75:1--75:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.75},
  URN =		{urn:nbn:de:0030-drops-64162},
  doi =		{10.4230/LIPIcs.ESA.2016.75},
  annote =	{Keywords: Online scheduling, deadlines, preemption with migration, competitive analysis}
}
Document
DOI: 10.4230/DagRep.5.7.1
Algorithms and Scheduling Techniques to Manage Resilience and Power Consumption in Distributed Systems (Dagstuhl Seminar 15281)

Authors: Henri Casanova, Ewa Deelman, Yves Robert, and Uwe Schwiegelshohn

Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)

Abstract
Large-scale systems face two main challenges: failure management and energy management. Failure management, the goal of which is to achieve resilience, is necessary because a large number of hardware resources implies a large number of failures during the execution of an application. Energy management, the goal of which is to optimize of power consumption and to handle thermal issues, is also necessary due to both monetary and environmental constraints since typical applications executed in HPC and/or cloud environments will lead to large power consumption and heat dissipation due to intensive computation and communication workloads. The main objective of this Dagstuhl seminar was to gather two communities: (i)~system-oriented researchers who study high-level resource-provisioning policies, pragmatic resource allocation and scheduling heuristics, novel approaches for designing and deploying systems software infrastructures, and tools for monitoring/measuring the state of the system; and (ii)~algorithm-oriented researchers, who investigate formal models and algorithmic solutions for resilience and energy efficiency problems. Both communities focused around workflow applications during the seminar, and discussed various issues related to the efficient, resilient, and energy efficient execution of workflows in distributed platforms. This report provides a brief executive summary of the seminar and lists all the presented material.
Cite as

Henri Casanova, Ewa Deelman, Yves Robert, and Uwe Schwiegelshohn. Algorithms and Scheduling Techniques to Manage Resilience and Power Consumption in Distributed Systems (Dagstuhl Seminar 15281). In Dagstuhl Reports, Volume 5, Issue 7, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{casanova_et_al:DagRep.5.7.1,
  author =	{Casanova, Henri and Deelman, Ewa and Robert, Yves and Schwiegelshohn, Uwe},
  title =	{{Algorithms and Scheduling Techniques to Manage Resilience and Power Consumption in Distributed Systems (Dagstuhl Seminar 15281)}},
  pages =	{1--21},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{7},
  editor =	{Casanova, Henri and Deelman, Ewa and Robert, Yves and Schwiegelshohn, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.1},
  URN =		{urn:nbn:de:0030-drops-56705},
  doi =		{10.4230/DagRep.5.7.1},
  annote =	{Keywords: Fault tolerance, Resilience, Energy efficiency, Distributed and high performance computing, Scheduling, Workflows}
}
Document
DOI: 10.4230/DagRep.3.9.106
Algorithms and Scheduling Techniques for Exascale Systems (Dagstuhl Seminar 13381)

Authors: Henri Casanova, Yves Robert, and Uwe Schwiegelshohn

Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)

Abstract
Exascale systems to be deployed in the near future will come with deep hierarchical parallelism, will exhibit various levels of heterogeneity, will be prone to frequent component failures, and will face tight power consumption constraints. The notion of application performance in these systems becomes multi-criteria, with fault-tolerance and power consumption metrics to be considered in addition to sheer compute speed. As a result, many of the proven algorithmic techniques used in parallel computing for decades will not be effective in Exascale systems unless they are adapted or in some cases radically changed. The Dagstuhl seminar "Algorithms and Scheduling Techniques for Exascale Systems" was aimed at sharing open problems, new results, and prospective ideas broadly connected to the Exascale problem. This report provides a brief executive summary of the seminar and lists all the presented material.
Cite as

Henri Casanova, Yves Robert, and Uwe Schwiegelshohn. Algorithms and Scheduling Techniques for Exascale Systems (Dagstuhl Seminar 13381). In Dagstuhl Reports, Volume 3, Issue 9, pp. 106-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{casanova_et_al:DagRep.3.9.106,
  author =	{Casanova, Henri and Robert, Yves and Schwiegelshohn, Uwe},
  title =	{{Algorithms and Scheduling Techniques for Exascale Systems (Dagstuhl Seminar 13381)}},
  pages =	{106--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{9},
  editor =	{Casanova, Henri and Robert, Yves and Schwiegelshohn, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.9.106},
  URN =		{urn:nbn:de:0030-drops-44199},
  doi =		{10.4230/DagRep.3.9.106},
  annote =	{Keywords: Exascale computing, high-performance computing and networking, fault-tolerance, power management, scheduling, numerical linear algebra}
}
Document
DOI: 10.4230/DagSemProc.06251.1
06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action

Authors: Hans-Dieter Burkhard, Martin Riedmiller, Uwe Schwiegelshohn, and Manuela Veloso

Published in: Dagstuhl Seminar Proceedings, Volume 6251, Multi-Robot Systems: Perception, Behaviors, Learning, and Action (2006)

Abstract
From 19.06.06 to 23.06.06, the Dagstuhl Seminar 06251 ``Multi-Robot Systems: Perception, Behaviors, Learning, and Action'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Hans-Dieter Burkhard, Martin Riedmiller, Uwe Schwiegelshohn, and Manuela Veloso. 06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action. In Multi-Robot Systems: Perception, Behaviors, Learning, and Action. Dagstuhl Seminar Proceedings, Volume 6251, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{burkhard_et_al:DagSemProc.06251.1,
  author =	{Burkhard, Hans-Dieter and Riedmiller, Martin and Schwiegelshohn, Uwe and Veloso, Manuela},
  title =	{{06251 Abstracts Collection – Multi-Robot Systems: Perception, Behaviors, Learning, and Action}},
  booktitle =	{Multi-Robot Systems: Perception, Behaviors, Learning, and Action},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6251},
  editor =	{Hans-Dieter Burkhard and Martin Riedmiller and Uwe Schwiegelshohn and Manuela Veloso},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06251.1},
  URN =		{urn:nbn:de:0030-drops-8444},
  doi =		{10.4230/DagSemProc.06251.1},
  annote =	{Keywords: Autonomous robots, multi-robot systems, object recognition, robot-human interaction, modeling, robot simulation}
}
Document
DOI: 10.4230/DagSemProc.06251.2
06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action

Authors: Uwe Schwiegelshohn, Walter Nistico, and Matthias Hebbel

Published in: Dagstuhl Seminar Proceedings, Volume 6251, Multi-Robot Systems: Perception, Behaviors, Learning, and Action (2006)

Abstract
The Dagstuhl Seminar on Multi-Robot Systems (06251) was held in June 20-23, 2006. It had the goal to bring researchers together from different areas of robotics to discuss current research topics on autonomous and interacting robots. The technical focus was on perception, behaviors, learning, and action. The seminar took directly place after the RoboCup robot soccer competitions and the subsequent symposium in Bremen. Thus researchers from many different countries were able to join the seminar and address issues without taking into account upcoming competitions or events.
Cite as

Uwe Schwiegelshohn, Walter Nistico, and Matthias Hebbel. 06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action. In Multi-Robot Systems: Perception, Behaviors, Learning, and Action. Dagstuhl Seminar Proceedings, Volume 6251, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schwiegelshohn_et_al:DagSemProc.06251.2,
  author =	{Schwiegelshohn, Uwe and Nistico, Walter and Hebbel, Matthias},
  title =	{{06251 Executive Summary – Multi-Robot Systems: Perception, Behaviors, Learning, and Action}},
  booktitle =	{Multi-Robot Systems: Perception, Behaviors, Learning, and Action},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6251},
  editor =	{Hans-Dieter Burkhard and Martin Riedmiller and Uwe Schwiegelshohn and Manuela Veloso},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06251.2},
  URN =		{urn:nbn:de:0030-drops-8432},
  doi =		{10.4230/DagSemProc.06251.2},
  annote =	{Keywords: Summary}
}
Document
DOI: 10.4230/DagSemRep.310
Management of Metacomputers (Dagstuhl Seminar 01241)

Authors: Francine D. Berman, Alexander Reinefeld, and Uwe Schwiegelshohn

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Francine D. Berman, Alexander Reinefeld, and Uwe Schwiegelshohn. Management of Metacomputers (Dagstuhl Seminar 01241). Dagstuhl Seminar Report 310, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{berman_et_al:DagSemRep.310,
  author =	{Berman, Francine D. and Reinefeld, Alexander and Schwiegelshohn, Uwe},
  title =	{{Management of Metacomputers (Dagstuhl Seminar 01241)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{310},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.310},
  URN =		{urn:nbn:de:0030-drops-151949},
  doi =		{10.4230/DagSemRep.310},
}
Document
DOI: 10.4230/DagSemRep.186
Parallel Scheduling (Dagstuhl Seminar 9729)

Authors: Ed Coffman, Ernst W. Mayr, and Uwe Schwiegelshohn

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ed Coffman, Ernst W. Mayr, and Uwe Schwiegelshohn. Parallel Scheduling (Dagstuhl Seminar 9729). Dagstuhl Seminar Report 186, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{coffman_et_al:DagSemRep.186,
  author =	{Coffman, Ed and Mayr, Ernst W. and Schwiegelshohn, Uwe},
  title =	{{Parallel Scheduling (Dagstuhl Seminar 9729)}},
  pages =	{1--1},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{186},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.186},
  URN =		{urn:nbn:de:0030-drops-150731},
  doi =		{10.4230/DagSemRep.186},
}
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