Name
Title | ||
|---|---|---|
Avoiding Unsafe States In Manufacturing Systems Based On Polynomial Digraph Algorithms |
Abstract | ||
|---|---|---|
A deadlock-free unsafe (DFU) state of Resource Allocation System (RAS) is deadlock-free but inevitable to enter a deadlock state. Previous research revealed that in many special systems, DFU states do not exist and polynomial deadlock avoidance policy (DAP) using one-step look ahead algorithms can avoid deadlock states. This paper first establishes the NP-completeness on determining the existence of DFU states. Then, giving necessary conditions of DFU states based on digraph analysis, it provides polynomial avoidance policies that inhibit loading new jobs to avoid DFU states. Furthermore, this method is generalized to mixed capacity systems and systems with flexible routings. Examples and simulation results are also presented. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/ROBOT.2003.1241913 | 2003 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-3, PROCEEDINGS |
Keywords | Field | DocType |
resource allocation,directed graphs,look ahead,polynomials,computational complexity | Polynomial,Computer science,Deadlock,Algorithm,Look-ahead,Production planning,Resource allocation,Deadlock prevention algorithms,Digraph,Computational complexity theory | Conference |
Volume | Issue | ISSN |
2 | 1 | 1050-4729 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yin Wang | 1 | 12 | 9.28 |
| Zhiming Wu | 2 | 0 | 0.34 |