摘要
中文摘要:柔性制造系统(FMS)是一种典型的离散事件动态系统(DEDS)。
本文对 Petri 网在其中的若干应用问题进行了较深入的研究。首先,对 Petri 网在 FMS
中的建模理论与方法做了一个较全面的综述。在前人启发式调度算法的基础上,通过
在网中引入资源成本的概念,在算法的执行过程中综合考虑时间成本和资源成本,实
现了资源成本与时间成本的多目标调度;通过在算法中对各机器虚成本的跟踪,动态
增加当前系统中负载较大机器的使用成本,降低其再被使用的机会,使得调度结果中
的各机器负载能相对均衡。调度算法均用 C 语言实现,并经实例验证。最后运用 CPN
仿真工具(CPNTools)对一个柔性制造单元进行了仿真研究,找出了其中物流策略的
不当之处,并提出改进方法。
Abstract: FMS is a typical DEDS. This paper makes a in-depth study of some
applications of Petri Net in it. First, a general survey about the modeling theory and method
of Petri Net for FMS is given. Based on previous heuristic scheduling algorithms,
multi-object scheduling of time and resource costs is implemented by introducing the
conception of resource costs into the net, considering time and resource costs synthetically
in the process. By tracing the virtual costs of machines in the algorithm, the using costs of
those heavy load machines are increased dynamically and their chances of being used again
are reduced, which results in a relative balance of machines loads in the scheduling result.
All these algorithms are implemented in C and verified by examples. At last, a CPN
simulation tool(CPNTools) is used to simulate a FMC. Some faults of its logistic strategies
are found and some improving methods are proposed.
引文
[1]. T.Murata, “Petri Nets: Properties,Analysis and Applications,”Proc.of
IEEE,Vol.77,No.4,pp.541-580,April 1989.
[2]. I.B.Abdallah,H.ElMaraghy and T.ElMekkawy,“An Efficient Search Algorithm
for Deadlock-free Scheduling in FMS Using Petri Nets,” In Proc.of 1998 IEEE Int.Conf.on
Robotics&Automation,pp.1793-1798,Leuven,Belgium,May 1998.
[3]. I.B.Abdallah,H.Elmaraghy, “Deadlock Prevention and Avoidance in FMS:A
Petri Net-Based Approach,”International Journal of Advanced Manufacturing
Technology,vol.16,no.1,1998.
[4]. M.D.Jeng and W.D.Chiou and Y.L.Wen,“Deadlock-Free Scheduling of Flexible
Manufacturing Systems Based on Heuristic Search and Petri Net Structures,”in Proc.IEEE
Int.Conf.Systems,Man,and Cybernetics.,pp.26-31,1998.
[5]. A.Reyes,H.Yu,and G.Kelleher, “Hybrid Heuristic Search for the Scheduling of
Flexible Manufacturing Systems Using Petri Nets,”IEEE trans.Robots.Automation,
pp.240-245,Vol.18,NO.2,April 2002.
[6]. M.D.Jeng,F.DiCesare, “Synthesis Using Resource Control Nets for Modeling
Shared-Resource Systems,”IEEE trans.Robotics.Automation,pp.317-327,Vol.11,NO.3,June
1995.
[7]. M.C.Zhou, F.DiCesare. “Parallel and sequential mutual exclusions for Petri net
modeling of manufacturing systems with shared resources,” IEEE Trans.Robot.and
Automat. Vol.7,no.4,pp.515-527,Aug.1991.
[8]. T.Aerwala, Y.Choed, “A synthesis rule for concurrent systems,” in Proc.Design
Automat.Conf.,1978,pp.305-311.
[9]. B.H.Krogh, C.L.Beck, “Synthesis of place/transition nets for simulation and
control of manufacturing systems,” in Proc.4th IFAC/IFORS Symp.Large Scale Syst.1986.
[10]. M.D.J, F.DiCesare, “A Review of Synthesis Techniques for Petri Nets with
Applications to Automated Manufacturing Systems,”IEEE trans.System,Man and
Cybe.,vol.23,no.1,pp.301-312.Jan,1993.
[11]. M.C.Zhou, F.DiCesare, “A Hybrid Methodology for Synthesis of Petri Net
Models for Manufacturing Systems,” IEEE trans.on Robotics and Automation,
Vol.8,No.3,pp.350-361,June 1992.
56 Petri 网在 FMS 中的若干应用研究
[12]. 袁崇义. Petri 网原理. 北京:电子工业出版社,1998. pp.51-54.
[13]. Richard Zurawski,M.C.Zhou, “Petri Nets and Industrial Applications: A
Tutorial,”IEEE trans.on Industrial Electronics,Vol.41,No.6,pp.567-583,December 1994.
[14]. G.Berthelot and R.Terrat, “Transformations and decompositions of nets,”in
advances in Petri Nets 1986.New York:Springer-Verlag,1986,pp.359-376.
[15]. Farvel K.H.Lee and J.Favrel, “Hierarchical reduction method for analysis and
decomposition of Petri nets,”IEEE Trans. Syst. Man. Cybern.,vol.SMC-15, pp.272-280,
May. 1985.
[16]. J.C.Mugarza, H.Camus “Reducing the Computational Complexity of Scheduling
Problems in Petri Nets by means of Transformation Rules,” in Proc.IEEE
Int.Conf.Systems,Man,and Cybernetics,pp.19-25,1998.
[17]. D.Y.Lee,F.Dicesare, “Scheduling Flexible Manufacturing Systems Using Petri
Nets and Heuristic search,”IEEE trans.on Robotics and Automation, Vol.10, No.2,
pp.123-132,April 1994.
[18]. H.H.Xiong,M.C.Zhou, “Scheduling of Semiconductor Test Facility via Petri
Nets and Hybrid Heuristic Search,”IEEE trans.Semiconductor Manufacturing, Vol.11, No.3,
pp. 384-392,August 1998.
[19]. J.Ezpeleta,J.M.colom,and J.Martinez, “A Petri Net Based Deadlock Prevention
Policy for Flexible Manufacturing Systems,”IEEE tans.on Robotics. Automation, Vol.11,
No.2,pp173-184,April 1995.
[20]. J.Liu,Y.Itoh, and I.Miyazawa, “A Research on Petri Net Properties using
Transitive Matrix,” in Proc.IEEE Int.Conf.Systems,Man,and Cybernetics.,pp.888-893,1999.
[21]. Y.J.Song,J.K.Lee, “Analysis of Petri net models using Transitive Matrix,” in
Proc.IEEE Int.Conf.Systems,Man,and Cybernetics.,pp.3122-3127,2000.
[22]. T.H.Sun,C.W.Cheng,and L.C.Fu, “APetri Net Based Approach to Modeling and
Scheduling for an FMS and a Case Study,”IEEE trans.on Industrial Electronics,
Vol.41,No.6,pp.593-601,December 1994.
[23]. J.H.Chen,L.C.Fu, and M.H.Lin, “Petri-Net and GA-Based Approach to
Modeling,Scheduling,and Performance Evaluation for Wafer Fabrication,”IEEE tans.on
Robotics andAutomation,Vol.17,No.5,October 2001.
[24]. B.C.Danasceno,X.L.Xie, “Petri Nets and Deadlock-free Scheduling of
Multiple-Resource Operations,” in Proc.IEEE Int.Conf.Systems,Man,and Cybernetics.,
参考文献 57
pp.878-883,1999.
[25]. M.Mori,C.C.Tseng, “A genetic algorithm for multi-mode resource constrained
project scheduling problem,”European Journal of Operational Research 100 (1997)
pp.134-141.
[26]. Y.W.Kim,A.Inaba,T.Suzuki, “FMS Scheduling Based on Petri net
Model,”Proc.of the 4th IEEE Int.Symp.on Assembly and Task Planning,pp.238-243,Soft
Research Park,Fukuoka,Japan,May 28-29,2001.
[27]. 张根保. 自动化制造系统.北京:机械工业出版社,1999.
[28]. Mullins, P.J., “Feeding Flexible Manufacturing Systems”, Automotive Industry,
Vol. 164,November 1984, pp. 63-4.
[29]. 郑大钟,赵千川.离散事件动态系统.北京:清华大学出版社,2001.PP.2-5.
[30]. 江志斌. Petri 网及其在制造系统建模与控制中的应用.安徽:合肥工业大学出
版社,1999.PP.14-40.
[31]. Mehdi,Kurapati. “Flexible Manufacturing Systems: An Overview.”International
Journal of Operations & Production Management, Vol. 14,No. 4, 1994, pp. 26-49.
[32] J.P.Reddy,S.Kumanan, “Application of Petri Nets and a GeneticAlgorithm to
Multi-Mode Multi-Resource Constrained Project Scheduling,” Int JAdv Manuf Technol
(2001) pp.305-314.
[33].A.Reyes,H.Yu,G.Kelleher,and S.Lloyd, “Integrating Petri Nets and hybrid
heuristic search for the scheduling of FMS,”Compuer In Industry ,47(2002),pp.123-138.
[34]. Ciaodo.G,Muppala.J, “SPNP:stochastic Petri net package.”In:Proceedings of the
Petri Nets and Performance Models,Kyoto,Japan,1989,142-151.
[35]. Lindemann.C, “DSPNexpress:a software package for the efficient solution of
deterministic and stochastic Petri nets.”Performance Evaluation,1995,22:3-21.
[36]. A.Furfaro,L.Nigro, “Distributed Simulation of Timed Colored Petri Nets,”2002.
[37]. Design/CPN Online. http://www.daimi.au.dk/designCPN/.
[38]. The CPN Group. http://www.daimi.au.dk/Cpnets.
[39]. 郑大钟,赵千川.离散事件动态系统.北京:清华大学出版社,2001.PP.230-236.
[40]. M.D.Jeng and S.C.Chen,“Heuristic Search Based on Petri Net Structures for
FMS Scheduling,”IEEE trans.Industry Applications.pp.196-202,vol.35,NO.1,JAN/FEB
1999.
[41].M.C.Zhou,M.D.Jeng, “Modeling,Analysis,Simulation,Scheduling,and Control of
Semiconductor Manufacturing Systems:A Petri Net Approach,” IEEE trans.Semiconductor
Manufacturing, Vol.11, No.3, pp. 333-357,August 1998.
[42] L. Ferrarini, “An incremental approach to logic controller design with Petri nets,”
IEEE Trans. Syst., Man, Cybern., vol. 22, pp. 461–473, 1992.
[43]. F.D.J.Bowden, “ABrief Survey and Synthesis of the Roles of Time in Petri
58 Petri 网在 FMS 中的若干应用研究
Nets,” Mathematical and Computer Modelling,vol.31(2000),pp.55-68.
[44]. D.Kuma,S.Harous, “Distruted Simulation of Timed Petri Nets:Basic Problems
And Their Resolution,” IEEE Trans. Syst. Man. Cybern.,vol.24, pp.1498-1510, Oct. 1994.
[45]. K. Jensen, Ed., Colored Petri Nets: Basic Concepts, Analysis Methods and
Practical Use, EATCS Monographs in Computer Science. Berlin, Germany:
Springer-Verlag, 1992.
[46]. Inseon Kon,F.Dicesare, “Synthesis Rules for Colored Petri Nets and Their
Applications to Automated Manufacting Systems,”Proc.of 1991 IEEE Int.Symp.on
Intelligence Control,pp.152-157,Arlington.Virginis.U.S.A, 13-15August 1991.
[47]. J. Kim, and A. A. Desrochers, “Modeling and analysis of semiconductor
manufacturing plants using time Petri net models: COT Business Case Study,” in Proc.
1997 IEEE Int. Conf. Systems Man Cybern., pp. 3227–3232, Orlando, FL, Oct. 12–15,
1997.
[48].Y. Narahari and N. Viswanadham, “A Petri net approach to the modeling and
analysis of flexible manufacturing systems,” Ann. Oper. Res., vol. 3, pp. 449–472, 1985.
[49]. M. C. Zhou and F. DiCesare, “Parallel and sequential mutual exclusions for Petri
net modeling for manufacturing systems,” IEEE Trans. Robot.Automat., vol. 7, pp.
515–527, Aug. 1991.
[50].M. C. Zhou, K. McDermott, and P. A. Patel, “Petri net synthesis and analysis of a
flexible manufacturing system cell,” IEEE Trans. Syst., Man, Cybern., vol. 23, pp. 523–531,
Mar./Apr. 1993.
[51]. A.Nagar,J.Haddock, S.Heragu, “Multiple and bicriteria scheduling: A literature
survey,”European Journal of Operational Research 81(1995)88-104.
[52]. J.Paulli, “A hierarchical approach for the FMS scheduling problem,” European
Journal of Operational Research 86(1995)32-42.
[53]. 汪应洛 系统工程理论方法与应用 北京:高等教育出版社 第二版 1998.
pp.132-161.
[54]. 顾启泰. 离散事件系统建模与仿真. 北京:清华大学出版社 1999.pp.1-5.
[55].http://wiki.daimi.au.dk:8000/cpntools-help/cpntools-help.wiki
[56]. Wells, L., B. Lindstr_ The Design/CPN Performance Tool Manual. Department
of Computer Science, University of Aarhus, 1998. On-line version: http://www.daimi.au.dk
/designCPN/
[57]. L.M.Kristensen, S. Christensen, K.Jensen, “The practitioner's guide to coloured
Petri nets” Int J STTT (1998) 2: 98-132
[58].吴启迪,严隽薇,张浩,“柔性制造自动化的原理与实践 ,” 北京:清华大学
出版社 1997 pp5-10.