Analysis of multi-stage open shop processing systems

C.E.J. Eggermont, A. Schrijver, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
67 Downloads (Pure)


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).
Originele taal-2Engels
TitelProceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS'11, Dortmund, Germany, March 10-12, 2011)
RedacteurenT. Schwentick, C. Dürr
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN van geprinte versie978-3-939897-25-5
StatusGepubliceerd - 2011

Publicatie series

NaamLIPIcs: Leibniz International Proceedings in Informatics
ISSN van geprinte versie1868-8968

Vingerafdruk Duik in de onderzoeksthema's van 'Analysis of multi-stage open shop processing systems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit