The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms

この論文にアクセスする

この論文をさがす

著者

抄録

The marking construction problem (<b>MCP</b>) of Petri nets is defined as follows: “Given a Petri net <i>N</i>, an initial marking <i>M<sub>i</sub></i> and a target marking <i>M<sub>t</sub></i>, construct a marking that is closest to <i>M<sub>t</sub></i> among those which can be reached from <i>M<sub>i</sub></i> by firing transitions.” <b>MCP</b> includes the well-known marking reachability problem of Petri nets. <b>MCP</b> is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (<b>MAXLFS</b>) or (ii) using an algorithm for <b>MAXLFS</b>. Moreover, this paper proposes four pseudo-polynomial time algorithms: <i>MCG</i> and <i>MCA</i> for (i), and <i>MCHF<sub>k</sub></i> and <i>MC_feideq_a</i> for (ii), where <i>MCA</i> (<i>MC_feideq_a</i>, respectively) is an improved version of <i>MCG</i> (<i>MCHFk</i>). Their performance is evaluated through results of computing experiment.

収録刊行物

  • IEICE transactions on fundamentals of electronics, communications and computer sciences

    IEICE transactions on fundamentals of electronics, communications and computer sciences 94(9), 1833-1841, 2011-09-01

    一般社団法人 電子情報通信学会

参考文献:  13件中 1-13件 を表示

各種コード

  • NII論文ID(NAID)
    10030190835
  • NII書誌ID(NCID)
    AA10826239
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • ISSN
    09168508
  • データ提供元
    CJP書誌  J-STAGE 
ページトップへ