Automatic generation of control solution for resource allocation using Petri net model
Geração automática da solução de controle para alocação de recursos utilizando redes de Petri
Nakamoto, Francisco Yastami; Miyagi, Paulo Eigi; Santos Filho, Diolino José dos
Abstract
The flexible manufacturing system (FMS) executes multiple processes simultaneously using a limited set of resources. These processes can be blocked permanently due to the sequence of the activities, i.e., the processes sharing a finite set of resources may eventually lead to a deadlock state. The FMS belongs to the class of discrete event systems where it is not possible to determine when an event will occur and the sequence of events becomes undefined. Such systems can be modeled using Petri net, and this work presents a method that solves the deadlock problem considering the indeterminism of FMSs. The goal of this work is to introduce an algorithmic approach, which allows the implementation of a computer program based on FMS functional specification. The proposal is to automate the generation of the control strategy for resource utilization and the rules to avoid the deadlock situation.
Keywords
Resumo
O sistema flexível de manufatura (FMS flexible manufacturing system) executa múltiplos processos simultaneamente que utilizam um conjunto limitado de recursos. Estes processos podem ficar permanentemente bloqueados em função da seqüência de atividades, isto é, o compartilhamento de um conjunto finito de recursos pode levar o sistema a um estado de autotravamento. O FMS pode ser visto como pertencente a uma classe de sistema a eventos discretos, onde não é possível determinar quando um evento ocorre e com isto a seqüência de eventos fica indefinida. Este tipo de sistema pode ser modelado através de rede de Petri e assim explora-se esta técnica para desenvolver uma solução para o problema de auto-travamento considerando o indeterminismo do FMS. O objetivo é introduzir uma abordagem algorítmica para a implementação de uma ferramenta computacional baseada na especificação funcional do FMS e que automatize a geração de uma estratégia de controle para a utilização de recursos e de regras para evitar o autotravamento.
Palavras-chave
References
BANASZAK, Z. A.; KROGH, B. H. Deadlock Avoidance In Flexible Manufacturing Systems with Concurrently Competing Process Flows. In: IEEE Transactions on Robotics and Automation, v. 6, p. 724-734, 1990.
BANASZAK, Z. A.; POLAK, M. Deadlock-free Distributed Control for Repetitive Flows. Proceedings of the Sixth International Workshop on Discrete Event Systems, p. 273-278, 2002.
CALINESCU, A.; EFSATHIOU, J.; SIVADAN, S., SCHIRN, J.; HUACCHO HUATUCI, L. Complexity in Manufacturing: An Information Theoretic Approach. In:Proceedings of the International Conference on Complex Systems and Complexity in Manufacturing, Warwick University, Warwick, 2000.
CASSANDRAS, C. G. Discrete Event Systems - Modeling and Performance Analysis, Richard D. Irvin, Inc. and Aksen Associates, Incorporated Publishers, p. 1-139, 1993.
CHO, H. An Intelligent Workstation Controller for Computer Integrated Manufacturing, Doctor dissertation, Texas A&M University, p. 83-88, 1993.
COFFMAN, E. G. JR.; ELPHICK, M. J.; SHOSHANI, A. System Deadlocks. In: Computing Surveys, v. 3, n. 2, p. 67-78, June 1971.
CORMEN, T. H., LEISERSON, C. E., RIVEST, E. L.; STEIN, C. Introduction to Algorithms, 2nd Edition, McGraw-Hill, 2003.
DROZDEK, A. Estrutura de Dados e Algoritmos em C++", Editora Pioneira Thomson Learning, 2002.
EDMONDS, B. What is Complexity? - The Philosophy of Complexity per se with Application to some Examples. In: Evolution, Symposium: The Evolution of Complexity, University of Brussels, Brussels, Belgium, 1995.
EZPELETA, J.; TRINCAS, F.; GARCIA VALLES, F.; COLOM, J. M. A Banker's Solution for Deadlock Avoidance in FMS with Flexible Routing and Multiresource States. In: IEEE Transactions on Robotics and Automation, v. 18, p. 621-625, 2002.
EZPELETA, J.; RECALDE, L. A Deadlock Avoidance Approach for Nonsequential Resource Allocation Systems. In: IEEE Transactions on Systems, Man and Cybernetics, Part A, v. 34, p. 93-101, 2004.
FANTI, M. P.; MAIONE, B.; MASCOLO, S.; TURCHIANO, B. Event-Based Feedback Control for Deadlock Avoidance in Flexible Production Systems. In: IEEE Transaction on Robotics and Automation, v. 13, n. 3, p. 347-363, 1997.
FANTI, M.P.; MAIONE, B.; MASCOLO, S.; TURCHIANO, B. Comparing Digraph and Petri Net Approaches to Deadlock Avoidance in FMS. In: IEEE Transaction on Systems, Man, and Cybernetics, v. 30, n. 5, p. 783-798, 2000.
HSIEH, F. S. Reconfigurable Fault Tolerant Deadlock Avoidance Controller Synthesis for Assembly Production Processes. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, v. 4, p. 3045-3050, 2000.
HSIEH, F. S. Modeling and Control of Holonic Manufacturing Systems Based on Extended Contract Net Protocol. In: Proceeding of the American Control Conference, v. 6, p. 5037-5042, 2002.
HO, Y. C.; CAO, X. R. Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academics Publishers, 1991.
ITO, Y. A Diserable Production Structure Lookin Toward the 21th Century - Anthropocentric Intelligence-Bases Manufacturing. XI Congresso Brasileiro de Engenharia Mecânica, São Paulo, Brazil, p. 23-32, 1991.
KUMARAN, T. K.; CHANG, W.; CHO, H.; WYSK, R. A. A Structured Approach to Deadlock Detection, Avoidance and Resolution in Flexible Manufacturing Systems. In: International journal of production research, v. 32, n. 10, p. 2361-2379, 1994.
LAWLEY, M.; REVELIOTIS, S.; FERREIRA, P. Design Guidelines for Deadlock Handling Strategies in Flexible Manufacturing Systems.In: The International Journal of Flexible Manufacturing Systems, v. 9, p. 5-30, 1997.
MIYAGI, P. E. Programmable Control: Fundaments of Discrete Event System Control. Sao Paulo: Ed. Edgard Blucher, 1996, (In Portuguese).
MURATA, T. Petri Nets: Properties, Analysis and Applications. In: Proceedings of the IEEE, v. 77, n. 4, p. 541-580, 1998.
NAKAMOTO, F. Y. Sistematização do Projeto do Controle de Sistemas Produtivos, Dissertação de Mestrado. Escola Politécnica da Universidade de São Paulo, São Paulo, Brazil, 2002. (In Portuguese. )
NAKAMOTO, F. Y.; MIYAGI, P. E.; SANTOS FILHO, D. J. Systematization of the Project of the Production System Control. IEEE International Symposium on Industrial Electronics, v. 2, p. 868-873, 2003.
NAKAMOTO, F. Y.; MIYAGI, P. E.; SANTOS FILHO, D. J. Resource Allocation Control in Flexible Manufacturing Systems Using the Deadlock Avoidance Method. In: Proceedings of COBEM 2007 - 19th International Congress of Mechanical Engineering, November 5-9, 2007, Brasília-DF.
PALAZZO, L. A. M.; CASTILHO, J. M. V. Complex Systems and Self-Organization. VI Regional School of Informatics, Curitiba, PR, Brazil, 1998. (In Portuguese. )
PETERSON, J. L. Petri Net Theory and the Modeling of Systems, Prentice-Hall, 1981.
REISIG, W. (1985) Petri Nets, an Introduction. Springer-Verlag, 1985. Berlin Heidelberg.
SANTOS FILHO, D. J. Aspectos do Projeto de Sistemas Produtivos. Tese de Livre Docência, Escola Politécnica da Universidade de São Paulo, São Paulo, Brazil, 2000. (In Portuguese).
VISWANADHAM, N.; NARAHARI, Y.; JOHNSON, T. L. Deadlock Prevention and Deadlock Avoidance in Flexible Manufacturing Systems Using Petri Net Models. In: IEEE Transactions on Robotics and Automation, v. 6, n. 6, p. 713-723, 1990.
ZIVIANI, N. Projeto de Algoritmos com implementações em PASCAL e C, Editora Thomson, 2004.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email