DROPS

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}
}

Search Results

Documents authored by Eggermont, Christian E.J.

Motion planning with pulley, rope, and baskets

Abstract

Cite as

Analysis of multi-stage open shop processing systems

Abstract

Cite as

Thanks for your feedback!

Could not send message