BibTex RIS Cite

SHORTEST PATH ALGORITHMS FOR PETRI NETS

Year 2016, Volume: 16 Issue: 2, 2073 - 2079, 23.09.2016

Abstract

Petri net is a mathematical and graphical tool for modeling and analysing discrete event systems. This paper focuses on a driving Petri net system from a given initial state to a desired state via minimum number of operations, that is, through the shortest transition sequence which is called as the shortest path problem. Thereby, two algorithms are developed to obtain the shortest path for Petri nets. The first algorithm, namely Forward Algorithm, uses integer programming approach and makes the process start from the initial state towards the desired state. The second algorithm, namely Backward Algorithm, uses most promising state to generate the shortest path and makes the process start from the desired state back to the initial state. Proposed algorithms do not deal with the reachability tree or graph of the net under analysis and use memory only for  storing the obtained paths unlike the approaches based on the reachability tree. Moreover, the algorithms can be applied to general Petri nets without any restriction. Simulation results demonstrate that the proposed algorithms reduces the computational time and complexity significantly..    

References

  • Desel, J., "Shortest paths in reachability graphs". Journal of Computer and System Sciences, 51:314–323,1995.
  • Desrochers, A. A. and Al-Jaar, R. Y. , "Applications of Petri nets in Manufacturing Systems", The Institute of Electrical Electrical and Electronics Engineers Inc., New York, 1995.
  • Kostin, A., "Reachability analysis in t-invariant- less Petri nets. IEEE Transactions on Automatic Control, 48, Issue: 6:10-19 1024, 2003.
  • Murata, T., "Petri nets: properties, analysis and applications" Proceedings of the IEEE, 77 No:4:541– 580, 1989.
  • Proth, J. and Xie, X. , "Petri Nets: A Tool for Design and Management of Manufacturing Systems. John Wiley & Sons, West Sussex, 1996.
  • Ru, Y. and C.N.Hadjicostis, "Reachability analysis for a class of petri nets , In Proceedings of IEEE Conference on Decision and Control, 2009, pp. 1261–1266, Shanghai.
  • S. Wang; M. Gan; M. Zhou; D. You, "A reduced reachability tree for a class of unbounded petri nets," in IEEE/CAA Journal of Automatica, 2, 4:345-352, 2015.
  • Y. Haoxiong and H. Yang, "Congested traffic based on ant colony algorithm for shortest path algorithm," in International Conference on Logistics, Informatics and Service Sciences (LISS),2015 , pp.1-3, July.
  • Y. Zheng; K. Hou; W. Liao and L.Yang., "The Shortest Path Algorithm Based on Petri Net," in 19th International Conference on Industrial Engineering and Engineering Management, 2013 , pp.221-229, April.
  • Apaydin-Özkan, H., “On Achieving Reachability Paths of Petri nets,” in 9th International Conference on Electrical and Electronics Engineering (ELECO), 2015, pp.724-728, November.
  • X. Ye, J. Z. and Song, X., “On reachability graphs of Petri nets”, Computers and Electrical Engineering, 29, 2:263-272, 2003.
  • M.Conforti, G.Cornuejols, G. Zambelli and Giacomo., "Integer Programming", Springer International Publishing, 2014.
  • E. Teruel, J. M. Colom, M. Silva, “Choice-free Petri nets: A model for deterministic concurrent systems with bulk services and arrivals”, IEEE Transactions on Systems, Man, and Cybernetics, 1(27): 73–83, 1997
Year 2016, Volume: 16 Issue: 2, 2073 - 2079, 23.09.2016

Abstract

References

  • Desel, J., "Shortest paths in reachability graphs". Journal of Computer and System Sciences, 51:314–323,1995.
  • Desrochers, A. A. and Al-Jaar, R. Y. , "Applications of Petri nets in Manufacturing Systems", The Institute of Electrical Electrical and Electronics Engineers Inc., New York, 1995.
  • Kostin, A., "Reachability analysis in t-invariant- less Petri nets. IEEE Transactions on Automatic Control, 48, Issue: 6:10-19 1024, 2003.
  • Murata, T., "Petri nets: properties, analysis and applications" Proceedings of the IEEE, 77 No:4:541– 580, 1989.
  • Proth, J. and Xie, X. , "Petri Nets: A Tool for Design and Management of Manufacturing Systems. John Wiley & Sons, West Sussex, 1996.
  • Ru, Y. and C.N.Hadjicostis, "Reachability analysis for a class of petri nets , In Proceedings of IEEE Conference on Decision and Control, 2009, pp. 1261–1266, Shanghai.
  • S. Wang; M. Gan; M. Zhou; D. You, "A reduced reachability tree for a class of unbounded petri nets," in IEEE/CAA Journal of Automatica, 2, 4:345-352, 2015.
  • Y. Haoxiong and H. Yang, "Congested traffic based on ant colony algorithm for shortest path algorithm," in International Conference on Logistics, Informatics and Service Sciences (LISS),2015 , pp.1-3, July.
  • Y. Zheng; K. Hou; W. Liao and L.Yang., "The Shortest Path Algorithm Based on Petri Net," in 19th International Conference on Industrial Engineering and Engineering Management, 2013 , pp.221-229, April.
  • Apaydin-Özkan, H., “On Achieving Reachability Paths of Petri nets,” in 9th International Conference on Electrical and Electronics Engineering (ELECO), 2015, pp.724-728, November.
  • X. Ye, J. Z. and Song, X., “On reachability graphs of Petri nets”, Computers and Electrical Engineering, 29, 2:263-272, 2003.
  • M.Conforti, G.Cornuejols, G. Zambelli and Giacomo., "Integer Programming", Springer International Publishing, 2014.
  • E. Teruel, J. M. Colom, M. Silva, “Choice-free Petri nets: A model for deterministic concurrent systems with bulk services and arrivals”, IEEE Transactions on Systems, Man, and Cybernetics, 1(27): 73–83, 1997
There are 13 citations in total.

Details

Journal Section Erratum
Authors

Hanife Apaydın Özkan

Publication Date September 23, 2016
Published in Issue Year 2016 Volume: 16 Issue: 2

Cite

APA Apaydın Özkan, H. (2016). SHORTEST PATH ALGORITHMS FOR PETRI NETS. IU-Journal of Electrical & Electronics Engineering, 16(2), 2073-2079.
AMA Apaydın Özkan H. SHORTEST PATH ALGORITHMS FOR PETRI NETS. IU-Journal of Electrical & Electronics Engineering. September 2016;16(2):2073-2079.
Chicago Apaydın Özkan, Hanife. “SHORTEST PATH ALGORITHMS FOR PETRI NETS”. IU-Journal of Electrical & Electronics Engineering 16, no. 2 (September 2016): 2073-79.
EndNote Apaydın Özkan H (September 1, 2016) SHORTEST PATH ALGORITHMS FOR PETRI NETS. IU-Journal of Electrical & Electronics Engineering 16 2 2073–2079.
IEEE H. Apaydın Özkan, “SHORTEST PATH ALGORITHMS FOR PETRI NETS”, IU-Journal of Electrical & Electronics Engineering, vol. 16, no. 2, pp. 2073–2079, 2016.
ISNAD Apaydın Özkan, Hanife. “SHORTEST PATH ALGORITHMS FOR PETRI NETS”. IU-Journal of Electrical & Electronics Engineering 16/2 (September 2016), 2073-2079.
JAMA Apaydın Özkan H. SHORTEST PATH ALGORITHMS FOR PETRI NETS. IU-Journal of Electrical & Electronics Engineering. 2016;16:2073–2079.
MLA Apaydın Özkan, Hanife. “SHORTEST PATH ALGORITHMS FOR PETRI NETS”. IU-Journal of Electrical & Electronics Engineering, vol. 16, no. 2, 2016, pp. 2073-9.
Vancouver Apaydın Özkan H. SHORTEST PATH ALGORITHMS FOR PETRI NETS. IU-Journal of Electrical & Electronics Engineering. 2016;16(2):2073-9.