Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets

Satoru OCHIIWA; Satoshi TAOKA; Masahiro YAMAUCHI; Toshimasa WATANABE

doi:10.1587/transfun.E92.A.2732

Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets

Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE

Full Text Views

0

Cite this

Summary :

The minimum initial marking problem of Petri nets (MIM) is defined as follows: "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 enabled at M₀ and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.11 pp.2732-2744

Publication Date: 2009/11/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E92.A.2732

Type of Manuscript: Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)

Category

Cite this

Copy

Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, "Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E92-A, no. 11, pp. 2732-2744, November 2009, doi: 10.1587/transfun.E92.A.2732.
Abstract: The minimum initial marking problem of Petri nets (MIM) is defined as follows: "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 enabled at M₀ and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2732/_p

Copy

@ARTICLE{e92-a_11_2732,
author={Satoru OCHIIWA, Satoshi TAOKA, Masahiro YAMAUCHI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets},
year={2009},
volume={E92-A},
number={11},
pages={2732-2744},
abstract={The minimum initial marking problem of Petri nets (MIM) is defined as follows: "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 enabled at M₀ and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.},
keywords={},
doi={10.1587/transfun.E92.A.2732},
ISSN={1745-1337},
month={November},}

Copy

TY - JOUR
TI - Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2732
EP - 2744
AU - Satoru OCHIIWA
AU - Satoshi TAOKA
AU - Masahiro YAMAUCHI
AU - Toshimasa WATANABE
PY - 2009
DO - 10.1587/transfun.E92.A.2732
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2009
AB - The minimum initial marking problem of Petri nets (MIM) is defined as follows: "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 enabled at M₀ and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.
ER -