Shortest Path Algorithms For Petri Nets

APAYDIN ÖZKAN H.

ISTANBUL UNIVERSITY-JOURNAL OF ELECTRICAL AND ELECTRONICS ENGINEERING, cilt.16, sa.2, ss.2073-2079, 2016 (ESCI) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 16 Sayı: 2
  • Basım Tarihi: 2016
  • Dergi Adı: ISTANBUL UNIVERSITY-JOURNAL OF ELECTRICAL AND ELECTRONICS ENGINEERING
  • Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI), Scopus, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.2073-2079
  • Anahtar Kelimeler: Petri net, Shortest path, Algorithms, REACHABILITY GRAPHS
  • Anadolu Üniversitesi Adresli: Evet

Özet

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.