Schedule Optimization of Time Petri Nets Based on Ant Colony Systems

Abstract:

This paper presents a time Petri net model with the optimizing mechanism based on ant colony systems that addresses the problem of schedule optimization. The choice rules and pheromone update rules of artificial ants are embedded into the evolution rules of a time Petri net, so the modeling and scheduling analysis of real systems can be integrated into the same model. Compared with the approaches based on the heuristic search and genetic algorithms, our method efficiently unifies the modeling and analysis of schedule problems based on a time Petri net.

• Periodical: Applied Mechanics and Materials (Volumes 263-266)
• Pages: 1733-1739
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.263-266.1733
• Online since: December 2012
• Authors: Xian Ming Liu*, Li Pan, Hong Zheng
• Keywords: Ant Colony System, Schedule Optimization, Time Petri Net

References

[1] P. Merlin and D. J. Farber, Recoverability of communication protocols: Implication of a theoretical study, IEEE Trans. Commun., vol. 24, no. 9, (1976) 1036-1043.

DOI: 10.1109/tcom.1976.1093424

[2] B. Berthomieu and M. Diaz, Modeling and Verification of Timed Dependent Systems Using Timed Petri Nets, IEEE Trans. Software Eng., vol. 17, no. 3, (1991) 259-273.

DOI: 10.1109/32.75415

[3] W. S. Liu Jane. Real-Timed Systems. Pearson Education, 2002.

[4] Zhibin Jiang. Petri Nets and their Applications to Modeling and Control for Manufacturing Systems. Beijing: China Machine Press, 2004 (In Chinese).

[5] D. Y. Lee and F. DiCesare, Scheduling flexible manufacturing systems using Petri Nets and heuristic search, IEEE Trans. Robotics and Automation, Vol. 10, No. 2, (1994) 123-132.

DOI: 10.1109/70.282537

[6] M. D. Jeng and S. C. Chen, Heuristic Search Based on Petri Net Structures for FMS Scheduling, IEEE Trans. on Industry Applications, Vol. 35, No. 1, (1999) 196-202.

DOI: 10.1109/28.740865

[7] H. H. Xiong and M. Zhou, Scheduling of semiconductor test facility via PN and hybrid heuristic search, IEEE Trans. on Semiconductor Manufacturing, Vol. 11, No, 3, (1998) 384-393.

DOI: 10.1109/66.705373

[8] N.Q. Wu, M. C. Zhou and F. Chu, A Petri Net-Based Heuristic Algorithm for Realizability of Target Refining Schedule for Oil Refinery, IEEE Transactions on Automation Science and Engineering, Vol. 5, Issue 4, (2008) 661-676.

DOI: 10.1109/tase.2008.916737

[9] H. Yu, A. Reyes, S. Cang and L S. loyd, Combined Petri Net modeling and AI-based heuristic hybrid search for flexible manufacturing systems - Part II. Heuristic hybrid search. Computers and Industrial Engineering, Vol. 44, No. 4,( 2003) 545-566.

DOI: 10.1016/s0360-8352(02)00213-9

[10] J. Lee and J. S. Lee, Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix, Computers & Industrial Engineering, vol. 59, (2010) 799-806.

DOI: 10.1016/j.cie.2010.08.006

[11] J. H. Chen, L. C. Fu, M. H. Lin, A. C. Huang, Petri-Net and GA-Based Approach to Modeling,Scheduling, and Performance Evaluation for Wafer Fabrication, IEEE Transactions on Robotics and Automation, Vol. 17, Issue 5,(2001) 619-636.

DOI: 10.1109/70.964663

[12] D. Hao, C. J. Jiang and L. Lin, Petri Net Based Modeling and GA Based Scheduling for FMS, Chinese Journal of Computers, Vol. 28, No. 2, (2005) 201-208. (In Chinese).

[13] T.C. Chiang, A. C. Huang and L. C. Fu, 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 Issue 3, (2006) 330-338.

DOI: 10.1109/tase.2005.862198

[14] X. Zhang and W. Zhang, Timed Petri Net Based Modeling and GA Based Schedul ing of Flexible Manufacturing System, Systems Engineering, Vol. 28, No. 11, (2010) 86-94. (In Chinese).

[15] J. Wang, G. Xu, and Y. Deng, Reachability Analysis of Real-Timed Systems Using Timed Petri Nets, IEEE Trans. Systems, Man, and Cybernatics, Part B, vol. 30, no 5,(2000) 725-736.

DOI: 10.1109/3477.875448

[16] T. Murata, Petri Nets: Properties, Analysis and Applications, Proc. IEEE, vol. 77, no.4, 1989, pp.541-580.

DOI: 10.1109/5.24143

[17] M. Boyer, and O. H. Roux, On the Compared Expressiveness of Arc, Place and Transition Timed Petri Nets, Fundamenta Informaticae, Volume 88, Issue 3,(2008) 225-249.

[18] M. Dorigo and T. Stützle, Ant colony optimization, MIT Press, 2004.