A Review of Colored Petri Nets and Their Applications for Manufacturing

Bài viết này là bài báo cáo hết môn của tôi cho môn học BPM (Business Process Management).

Tôi đã định viết về các loại công cụ mô hình hóa/mô phỏng các quá trình công nghiệp (ví dụ: Manufacturing) từ lâu nhưng chưa có điều kiện. Bài viết này sau sẽ được biên tập lại cho súc tích và dễ hiểu hơn cũng như sẽ có bản tiếng Việt.

Các bạn chỉ cần nhận thấy rằng có rất nhiều hướng thú vị cũng như các công cụ đủ mạnh để nghiên cứu về các quá trình thực tế thì bài giới thiệu này coi như đã thành công.

Do viết vội chỉ trong 6 tiếng đồng hồ nên có một số đoạn còn chưa khúc chiết & chuẩn xác về cả chuyên môn & tiếng Anh, chúng sẽ được sửa chữa sau.

Bài này dành cho các bạn sinh viên quan tâm đến nghiên cứu khoa học có thể tham khảo. Tuy nhiên, chất lượng của nó chỉ dừng trong khuôn khổ lớp học & để luyện viết tiếng Anh Kỹ thuật, không phải là bài báo gửi đăng tạp chí chuyên ngành, xin lưu ý

A Review of Colored Petri Nets and Their Applications for Manufacturing

Tuan Tran

Department of Industrial and Systems Engineering, Dongguk University, Seoul, Korea

A Report for BPM Class, Fall Semester, 2011

Abstract

In this paper, the author reviews four cases of apply CPN in manufacturing. It is found that CPN is widely used for manufacturing and CPN with or without suitable modifications can be used to model manufacturing systems for various products with various levels of modeling quality and various qualitative and quantitative modeling results. Through this review paper, the evolution of CPN through more than two decades as well as the evolution of computational approach to CPN applications in manufacturing has been shown. The author also suggests combining CPN and trends of collaboration, globalized production, internet and cloud computing to gain the next level of development of CPN applications for manufacturing.

Keywords: Colored Petri Nets, CPN, Manufacturing, FMS, Manufacturing systems, Petri nets applications.

1.      Introduction

1.1  Petri Nets

Petri Nets are graphical and mathematical modeling tool applicable to many systems. They are promising tool for describing and studying information processing systems that are characterized as being concurrent, asynchronous, distributed, parallel, nondeterministic, and/or stochastic [Murata, 1989].

A Petri net is a directed bipartite graph, in which the nodes represent transitions (i.e. events that may occur, signified by bars) and places (i.e. conditions, signified by circles). The directed arcs describe which places are pre – and/or post – conditions  for which transitions (signified by arrows) [Wikipedia]

Petri Nets were invented in by Carl Adam Petri initially for the purpose of describing chemical processes. Like industry standards such as UML activity diagrams or BPMN, Petri nets offer a graphical notation for processes that include choice, iteration, and concurrent execution. Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis.

A Petri net is marked by placing “tokens” on places. When all the places with arcs to a transition (its input places) have a token, the transition “fires”, removing a token from each input place and adding a token to each place pointed to by the transition (its output places). Variants on the basic idea include the Event Condition Nets, Place Transition Nets, Colored Petri Net (CPN), Timed Petri Net, Stochastic Petri Net, and Predicate Transition Net and some other types.

Figure 1 shows an example of a Petri Net

Fig. 1. An example of a Petri Nets

1.2  Colored Petri Nets

Colored Petri Nets (CPN) are the Petri Nets with color feature, which allows tokens to have values. They are used for systems where synchronization, communication, and resource sharing are important. CPN models are validated by means of simulation. CPN models are dynamic. They can be executed on a computer and allow us to play and investigate different scenarios.

Example of CPN is given in Figure 2.

Fig. 2. Example of CPN

Colored Petri Nets (CPNs) have been used in a wide variety of domains: communication (protocols and data networks), software design (Mobile phones, RPC mechanisms, etc.), hardware (Superscalar processors, VLSI Chips, etc.), control systems (alarm systems, train control systems, etc.), military systems (command and control systems, planning, etc.).

Petri nets  (PN), especially CPN, are  being applied  in  the modeling, analysis and control of discrete manufacturing  systems [Racalde et al., 2003].  The  ability  of  CPN  to  model concurrent,  synchronized  interactions  within  a  manufacturing system  has  contributed  to  their  development as  a  powerful modeling tool.  CPN  describe  a  manufacturing  system  graphically,  and  this  contributes  to  a better understanding of the complex interactions within the  system [Cecil et al., 1992].

In this paper, we will review four cases of apply CPN in manufacturing systems. Through the review of papers, we can see the wide range of applications of CPN in manufacturing domain, understand the solvability differences among variations of CPN as well as to asset the evolution of CPN through decades and the implementation of computational tools.

2.      Literature Review

In this part, we will review four papers with four cases of apply CPN in manufacturing. For each case, a modified version of CPN is used.

2.1  Pure Colored Petri Nets

Pure CPN models are used for automated manufacturing systems by Viswandham et al. [1987]. In this work, the authors propose an approach, using CPN for modeling flexible manufacturing systems (FMS). The authors illustrate their methodology for a flexible manufacturing cell (FMC) with three machines and three robots.

The authors consider CPN with fininte number of places, finite number of transitions and finite color sets. They establish the usefulness of CPN as a compact modeling tool for the description of automated manufacturing systems as well as show the modeling power of CPN and their use to investigate deadlock investigation.

Fig. 3. CPN model of an FMC with three machines and three robots (Viswandham et al., 1987)

2.2  Colored Timed Petri Nets

Colored Timed Petri Nets (CTPN)  extend the  framework of the  original PN  by  adding  color  and  time  attributes  to  the  net. (CPTN) are used by Kuo et al. [1997] together with the consideration of statistical process control (SPC) and fault diagnosis (FD) to model FMS with high assurance of quality consistence and machines’ utilization of the systems.

They are SPC and FD to be the additional functionalities to CTPN to come up with a more powerful modeling tool for FMS compared to original CTPN.

In the work of Kuo et al. [1997], the CTPN based SPC and  FD models  are proposed  to  model  the  FMS’s SPC and  fault  diagnosis  behaviors.

Since  the  models  depend on  the  measured  data  from  the  inspection  machines  and the sensors’ data  from the devices, the CTPN-based  SPC and  FD models  can  be  incorporated  into  the production  CTPN  models  to  give  a  complete  model  of FMS’s activities.

It is argued that the  CTPN-based  fault diagnosis  is  easy  to  model,  and  the  results  are straightforward.

In the work of Chiang et al. [2006], a combination of CTPN and queueing systems is introduced with a special kind of transition named the queueing transition implemented into the CTPN to represent the role of the queueing system.

The modeling power of CTPN is exploited to elegantly model processing capability

and routing while the queueing system is used to simplify the model and accelerate the execution.

In this work, Queueing Colored Petri Nets (QCPN) is used for performance evaluation and scheduling for wafer fabrication. The main idea of this tool is to combine CPTN with the queueing systems (QS), and it aims to make simulation over the model more efficient.

It is argued that QCPN-based genetic algorithm (GA) scheduler can greatly reduce the computation time so that this GA scheduler can meet the need for a rapidly changing environment. The proposed QCPN-based simulator is efficient and accurate, and the GA scheduler, which uses the proposed simulator as the evaluation function, is the potential to set priority rules quickly, automatically, and intelligently so that schedules with satisfactory performance measures can be generated.

Fig. 5. QCPN – based equipment module (Chiang et al., 2006)

To cope with the rapid change in manufacturing market requirements, reconfigurable manufacturing systems (RMS) model with the feature of reconfigurability has been proposed by Meng et al. [2010]. This model describes the reconfiguring process of a manufacturing system and is developed by applying Colored Timed Object Oriented Petri Nets (CTOOPN).

Based on the main difference between configurations of RMS and FMS, a modular hierarchical structure of RMS is developed. By the object oriented method, all the object classes in the RMS model are identified.

A macro-place is used to model the aggregation of many processes and a macro-transition is used to link all the related macro-places. Macro-places and macro-transitions are connected with arcs to form a Petri net named a macro-level Petri net so that the control logic of RMS is represented.

The macro-level Petri net is refined by hierarchical steps, each step describing these macro-places by more detailed sub macro-places until all the macro-places cannot be divided. Then the characteristics of material flow and time constraints in RMS are modeled by applying colored tokens and associated time-delay attributes. This model integrates object-oriented methods, stepwise refinement ideas and Petri nets together. The RMS activities can be encapsulated and modularized by the proposed method, so that RMS can be easily constructed and investigated by the system developers.

Fig. 6. System level CPN model of the example RMS by Renew (Meng et al., 2010)

3.      Discussions

3.1  Range of Colored Petri Nets Applications in Manufacturing

Various applications of CPN are used in manufacturing domain, ranging from automated, flexible manufacturing to reconfigurable manufacturing systems with different kinds of products, machines, tools and equipments.

It is shown that CPN can be used, with or without modifications and combinations to qualitatively or quantitatively model manufacturing systems.

CPN can be flexibly used to model various kinds of manufacturing systems.

3.2  Solvability differences among variations of Colored Petri Nets

Solvability of CPN tools for manufacturing systems varies from simply modeling a manufacturing system to modeling and estimating parameters of a manufacturing system with high degree of accuracy.

For simple systems, such as the case in the work of Viswandham et al. [1987], a pure CPN should be powerful enough to model the system. For more complex systems, such as the one in the work of Kuo et al. [1997], considerations of systems’ characterized factors should be made and the CPN itself should be modified to be equipped with additional features, i.e time feature to become a new CTPN tool in order to be powerful enough to model the systems.

For even more complex systems, such as the one in the work of Chiang et al. [2006] and Meng et al. [2010], CPN can be combined with other techniques such as queueing systems or object oriented approaches to improve the modeling ability as well modeling accuracy.

CPN, with suitable modifications, can give various levels of good solutions for modeling manufacturing systems.

3.3  Evolution of Colored Petri Nets and the implementation of Computational Tools

Through the four cases reviewed in this paper, we can see that CPN has had a great evolution, from a simple modeling tool to describe the system qualitatively to a powerful, flexible and extensible tool to quantitatively model and estimate manufacturing systems’ parameters.

CPN implementation in manufacturing gains better and better modeling quality and accuracy and speed of algorithms increases through the years.

For the very first cases of CPN application in manufacturing, there is only qualitative model and there is no computer program to be made [Viswandham et al.,1987], but for later cases, since the algorithms themselves are better and the approaches offer quantitative results, simulators and schedulers can be made as the output of the researches and computational programs can be created will higher and higher computational ability [Kuo et al., 1997] [Chiang et al., 2006] [Meng et al., 2010].

4.      Conclusions

In this paper, the author reviews four cases of applying CPN with different modifications to manufacturing domain.

It is found that CPN is widely used for manufacturing and CPN with or without suitable modifications can be used to model manufacturing systems for various products with various levels of modeling quality and various qualitative and quantitative modeling results.

Through this review paper, the evolution of CPN through more than two decades as well as the evolution of computational approach to CPN applications in manufacturing has been shown.

As of today, the trends of collaboration in manufacturing as well as the scenario of globalized and distributed production is dominant, and the utilization of internet environment and cloud computing is interested by many enterprises, CPN may find the next level of  development for itself by combining with those trends mentioned above.

References

Cecil et al., A Review of Petri Net Applications in Manufacturing, International Journal of Advanced Manufacturing Technology 7, 1992

Chiang et al., Modeling, Scheduling, and Performance Evaluation for Wafer Fabrication: A Queueing Colored Petri-Net and GA-Based Approach, IEEE Transactions on Automation Science and Engineering, Vol. 3, No. 3, July 2006

Kuo et al., Colored Timed Petri Net Based Statistical Process Control and Fault Diagnosis to Flexible Manufacturing Systems, Proceedings of the 1997 IEEE International on Robotics and Automation, Albuquerque, New Mexico, April 1997

Meng et al., Modeling of Reconfigurable Manufacturing Systems Based on Colored Timed Object – Oriented Petri Nets, Journal of Manufacturing Systems, 29, 2010, pp. 81–90

Murata T., Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, Vol. 77, No. 4, April 1989

Recalde et al., Petri Nets and Manufacturing Systems: An Examples-Driven Tour, Proc. Lectures on Concurrency and Petri Nets, 2003, pp.742-788

Viswandham et al., Coloured Petri Net Models for Automated Manufacturing Systems, Proceedings of the IEEE International Conference on Robotics and Automation, 1987

Nova @ MES Lab.