Masters' Theses A study on an efficient real-time deadlock-free control algorithm by using graph-theoretic approach
2015.07.29 12:24
| year | 1998 |
|---|---|
| author | Jungwoon Yoo |
| Keyword | A study on an efficient real-time deadlock-free control algorithm by using graph-theoretic approach |
| Abstract | In line with the rapid development of computer and automation technologies, most of today´s manufacturing systems have volved toward automated systems because they have the potential for providing a high level of performance, i.e. high roductivity, reduction of lead time, high adaptability in continuously changing demands. One of the most popular and promising automated systems is the so-called Flexible manufacturing systems(FMSs). FMSs aim to achieve flexibility with respect to physical structure and logical structure. As such FMSs induce interests of many researchers to study better methods for the design, operation, and performance evaluation of FMSs. Among these various research areas in FMS, one area that has often been overlooked is related to a deadlock problem. More recently, the deadlock issues receive considerable attention in the real-time control realm of automated manufacturing system. An FMS deadlock refers to a situation where two or more parts that have finished current processing each wait for the next machine occupied by other part so that further part flow is inhibited. When an FMS enters deadlock, the whole system can cease to operatae in spite of no apparent machine failure. Deadlock makes part of the system inoperable and gradually expands to the whole system and at last may result in permanent blocking state. As a result, the system utilization and the productivity of the system are decreased. Deadlock-free operation, therefore, is a principle requirement of FMS control. Many researchers studied on an deadlock by using various modelling techniques, especially Petri-net. Modelling an FMS is a time-consuming task in itself. To make the matters worse, whenever a small change in a physical layout(structure) and/or a logical structure occurs, it takes too much time to revise the model. The revision of the model causes the whole changes of the existing model. As the market changes into multi-product small-production environment, an FMS has many physical and logical changes. That´s why such In this paper, we apply a simple and easily adaptable deadlock avoidance algorithm to a middle-sized FMS. This algorithm uses a graph-theoretic approach. It is proposed by Kim(1997). Unlike Petri-net based methods which are complex and static, it is easy to modify the existing model as the system configuration is changed. Most papers on an deadlock dealt with a very small system as an object of research( i.e. 2 machines and 1 AVG or Robot ). Therefore, even though they included an AGV into their system, they had only to focus on the part flow deadlock problem without considering it. On the other hand, the FMS, the object of our research, is equipped with # machines and # AGVs and # robots. We take both the AGV deadlock problem and the part flow deadlock problem into considerations. The core of this paper consists of two parts : AGV deadlock avoidance algorithm by using graph-theoretic approach and the integration of part flow deadlock avoidance and AGV deadlock avoidance. ( if possible tool deadlock avoidance ) In particular, the integration of part flow deadlock avoidance and AGV deadlock avoidance is of importance in this paper. Until now, some researches have been focused on the part flow deadlock avoidance and others on the AGV deadlock avoidance. Few papers dealt with both the AGV deadlock and the part flow deadlock. In this paper, we propose the augmented graph-theoretic approach which can resolve two kinds of deadlock at the same method and in one model. We apply this new approach to virtual manufacturing system we design. Throughout this paper, we propose a new deadlock avoidance method which can integrate the part flow deadlock avoidance and the AGV deadlock avoidance. This deadlock avoidance algorithm can be easily modified whenever the structures will be changed. Therefore, it is fit for FMS, because FMS has much opportunity for changing its structure. Moreover, as it is very simple, it is appropriate for real-time control mechanism. |
| c | MS |
Download :