Analysis of multi-stage open shop processing systems

Details Analysis of multi-stage open shop processing systems Analysis of multi-stage open shop processing systems

2011-02-15

arxiv.org/abs/1102.3029v1

Computer Science

Data Structures and Algorithms

19 pages, no figures

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Analysis of multi-stage open shop processing systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of multi-stage open shop processing systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of multi-stage open shop processing systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378243