Title :
A new heuristic method for solving the minimum initial marking problem of Petri nets
Author :
Nishi, Shin´ichiro ; Taoka, Satoshi ; Watanabe, Toshimasa
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
The paper proposes a novel heuristic algorithm FMDB for the minimum initial marking problem MIM of Petri nets: “Given a Petri net and a firing count vector X, find an initial marking M, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is firable on M and the rest can be fired one by one subsequently”. Experimental results show that FMDB produces better solutions than any known algorithm
Keywords :
Petri nets; heuristic programming; minimisation; resource allocation; FMDB; MIM; Petri nets; firing count vector; heuristic algorithm; heuristic method; minimum initial marking problem; minimum total token number; Circuits and systems; Facsimile; Feedback; Heuristic algorithms; Law; Legal factors; Petri nets; Resource management; Systems engineering and theory; Terminology;
Conference_Titel :
Systems, Man, and Cybernetics, 2000 IEEE International Conference on
Conference_Location :
Nashville, TN
Print_ISBN :
0-7803-6583-6
DOI :
10.1109/ICSMC.2000.886497
