2 Search Results for "Eggermont, Christian E.J."

Document
DOI: 10.4230/LIPIcs.STACS.2012.374
Motion planning with pulley, rope, and baskets

Authors: Christian E.J. Eggermont and Gerhard J. Woeginger

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We study a motion planning problem where items have to be transported from the top room of a tower to the bottom of the tower, while simultaneously other items have to be transported into the opposite direction. Item sets are moved in two baskets hanging on a rope and pulley. To guarantee stability of the system, the weight difference between the contents of the two baskets must always stay below a given threshold. We prove that it is Pi-2-p-complete to decide whether some given initial situation of the underlying discrete system can lead to a given goal situation. Furthermore we identify several polynomially solvable special cases of this reachability problem, and we also settle the computational complexity of a number of related questions.
Cite as

Christian E.J. Eggermont and Gerhard J. Woeginger. Motion planning with pulley, rope, and baskets. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 374-383, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{eggermont_et_al:LIPIcs.STACS.2012.374,
  author =	{Eggermont, Christian E.J. and Woeginger, Gerhard J.},
  title =	{{Motion planning with pulley, rope, and baskets}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{374--383},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.374},
  URN =		{urn:nbn:de:0030-drops-33900},
  doi =		{10.4230/LIPIcs.STACS.2012.374},
  annote =	{Keywords: planning and scheduling; computational complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.484
Analysis of multi-stage open shop processing systems

Authors: Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).
Cite as

Christian E.J. Eggermont, Alexander Schrijver, and Gerhard J. Woeginger. Analysis of multi-stage open shop processing systems. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 484-494, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{eggermont_et_al:LIPIcs.STACS.2011.484,
  author =	{Eggermont, Christian E.J. and Schrijver, Alexander and Woeginger, Gerhard J.},
  title =	{{Analysis of multi-stage open shop processing systems}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{484--494},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.484},
  URN =		{urn:nbn:de:0030-drops-30373},
  doi =		{10.4230/LIPIcs.STACS.2011.484},
  annote =	{Keywords: scheduling, resource allocation, deadlock, computational complexity}
}
  • Refine by Author
  • 2 Eggermont, Christian E.J.
  • 2 Woeginger, Gerhard J.
  • 1 Schrijver, Alexander

  • Refine by Classification

  • Refine by Keyword
  • 1 computational complexity
  • 1 deadlock
  • 1 planning and scheduling; computational complexity
  • 1 resource allocation
  • 1 scheduling

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012

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 About DROPS Imprint Privacy Contact