An Analytical Investigation of the Deadlock Avoidance Versus Detection and Recovery Problem in Buffer-Space Allocation of Flexibly Automated Production Systems
Spyros A. Reveliotis · 2000
Motivated by recent developments in the semicon- ductor manufacturing industry, this paper undertakes an analyt- ical investigation of the problem of selecting optimally the dead- lock resolution strategy for buffer space allocation in flexibly au- tomated production systems. In the process, it extends the behav- ioral models for the aforementioned systems currently considered in the literature, to account for probabilistic uncontrollable effects like the requirement for extra finishing steps and/or rework, and it introduces a new deadlock resolution scheme, characterized as randomized deadlock avoidance. The combination of these two ex- tensions brings the considered system behavior(s) to the realm of probabilistic automata, an area of increasing academic interest. For the resulting model, and under the assumption of Markovian timings, it develops an analytical methodology for selecting the op- timal deadlock resolution strategy that maximizes the steady-state system throughput, and it demonstrates its effectiveness through application to a prototype system configuration. The obtained results provide an interesting analytical expression of the need to assess the gains obtained by the increased concurrency supported by the deadlock detection and recovery strategy versus the pro- ductivity losses experienced under this approach due to increased system blocking, and/or additional material handling overheads. It turns out that, for the considered system configuration, the optimal selection scheme switches between detection and recovery and pure deadlock avoidance, every time that the time cost of deadlock re- covery, , crosses a threshold , which is a function of the re- maining system behavioral and timing parameters. Beyond its own theoretical merit, this last result raises also the question of whether the policy randomization introduced in this work will ever enhance the performance of any configuration in the considered class of Re- source Allocation Systems (RAS); this issue will be investigated in a sequel paper.