- Analysis of multi-stage open shop processing systems
- Leibniz International Proceedings in Informatics
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
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).
- go to publisher's site
- Proceedings title: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Place of publication: Wadern
Editors: Th. Schwentick, Ch. Dürr
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.