The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
페트리네트의 최소 초기 마킹 문제(MIM)는 다음과 같이 정의됩니다: "페트리 네트와 발사 횟수 벡터가 주어지면 X, 초기 표시 찾기 M0, 각 전환이 다음과 같은 전환 시퀀스 δ가 있는 최소 총 토큰 수를 사용합니다. t 정확하게 나타납니다 X(t) 번 δ에서 첫 번째 전환이 활성화됩니다. M0 나머지는 순차적으로 해고될 수 있습니다." 공장 자동화와 같은 생산 시스템에서 작업 처리 일정을 실행할 수 있는 초기 자원의 경제적인 분배는 다음과 같이 공식화될 수 있습니다. MIM. AAD 기존 알고리즘 중에서 가장 좋은 솔루션을 생성하는 것으로 알려져 있습니다. 비록 솔루션은 아밈+ 다음보다 더 나쁩니다. AAD, 알려진 바는 아밈+ 매우 빠릅니다. 본 논문에서는 새로운 휴리스틱 알고리즘을 제안한다. AADO 및 AMDLO, 기존 알고리즘의 개선된 버전 AAD 및 아밈+, 각각. 솔루션의 선명도나 짧은 CPU 시간이 주요 목표입니다. AADO or AMDLO, 각각. 컴퓨팅 실험을 기반으로 초기 마킹의 평균 총 토큰 수는 다음과 같습니다. AADO 에 비해 약 5.15% 적습니다. AAD, 그리고 평균 CPU 시간은 AADO 그 중 약 17.3%이다. AAD. AMDLO 다음 솔루션보다 약간 더 나쁜 솔루션을 생성합니다. AAD에 비해 약 10.4% 더 우수합니다. 아밈+. CPU 시간은 AMDLO 의 약 180배이다. 아밈+, 여전히 빠릅니다: 평균 CPU 시간 AMDLO 의 약 2.33%이다. AAD. 일반적으로 입력 인스턴스의 크기가 증가함에 따라 솔루션이 악화되는 것으로 관찰되며 이는 다음과 같은 경우입니다. AAD 및 아밈+. 이러한 바람직하지 않은 경향은 다음에서 크게 개선되었습니다. AADO 및 AMDLO.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
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 M0, 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 M0 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
부
@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 M0, 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 M0 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},}
부
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 M0, 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 M0 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 -