数理計画法による離散事象システムの動作解析とその応用

离散事件系统的数学规划行为分析及其应用

• 批准号: 08650460
• 负责人: MATSUMOTO Tadashi
• 金额: $ 1.47万
• 依托单位: Faculty of Engineering, Fukui University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08650460/
• 关键词: Discrete event systems; reachability; Petri nets; executable firing sequences; mathematical programmings; invariants; live systems; critical siphons; ペトリネット; スケジューリング; 動的計画法; ポントリヤギンの最小原理; 線形計画法; サイフォン・トラップネット; 擬似解

In this research, we obtained some mathematical programming approaches to reachability problems for place-transition Petri nets which are one of typical models for various kinds of discrete event dynamical systems.An algorithm for the executable firing sequence with the shortest length in the submarking reachability problems (i.e. SMR) is given by general discrete-time Pontryagin s mini mum principle included linear programmings (i.e., "PMP+LP" ).We also obtained algorithms for the executable firing sequence with the prescribed length in the basic marking reachability problems with the known firing count. vector (i.e., MR-FV) via special "PMP+LP" as well as "DP+LP" (i.e., the dynamic programming included linear programmings).These algorithms divide die original problem into d smaller subproblems and have semi-polynomial time complexity provided that checking critical siphons, which is an important future research problem, is neglected, where d is the length of firing sequence of transitions.Note that SMR (MF-FV, resp.) is the most, fundamental reachability problem without (with, resp.) the known firing count vector in si-ate equation of Petri nets.For MR-FV, a new reachability criterion is also given, that is, the reachability for a given Petri net is reduced to one for each strongly-connected and maximal siphon because the firing count vector in MR-FV is in advance specified. Another approach to finding the executable firing sequence in MR-FV by using T-invariants and the extended particular solution of state equation. This approach is expected to be useful for reachability problems of live free-choice Petri nets.

本文研究了离散事件动态系统的典型模型之一-位置变迁Petri网的可达性问题的数学规划方法，利用包含线性规划的广义离散时间Pontryagin极小值原理（即，在基本的标记可达性问题中，我们也得到了在已知触发次数的情况下，具有指定长度的可执行触发序列的算法。矢量（即，MR-FV）通过特殊的“PMP+LP”以及“DP+LP”（即，这些算法将原问题分解为d个更小的子问题，并具有半多项式的时间复杂度，其中d是触发转移序列的长度。是最基本的可达性问题，而不需要（分别）对于MR-FV，给出了一个新的可达性判据，即由于MR-FV中的触发计数向量是预先确定的，因此对于每个强连通的最大虹吸，给定的Petri网的可达性约为1.利用T-不变量和状态方程的扩展特解求MR-FV中可执行触发序列的另一种方法。这种方法有望对自由选择Petri网的可达性问题的研究有所帮助。

项目成果

T.Matsumoto, K.Saikusa: "Minimum Number of Live Minimal Structural Traps to Make a Minimal Deadlock Locally Live in General Petri Nets" IEICE Trans. on Funds. of ECCS. Vol.E81-A.No.1. 164-174 (1998. 01)

T.Matsumoto、K.Saikusa：“在一般 Petri 网中局部产生最小死锁的最小数量的实时最小结构陷阱”IEICE Trans。

T.Matsumoto: "A minimum principle of Ponyryagin in optimal nonlinear discrete-time systems with terminal constraints and free terminal time and its applications to reachability problems of discrete event systems" Procs.of Japan-USA Symposium on Flexible A

T.Matsumoto：“具有终端约束和自由终端时间的最优非线性离散时间系统中的 Ponyryagin 最小原理及其在离散事件系统可达性问题中的应用”Procs.of Japan-USA Symposium on Flex A

T.Matsumoto, Ahmed Tarek: "Finding legal firing sequence of Petri nets by means of dynamic programming included linear programming" Procs.of The 35the IEEE Conf.on Decision and Control. 4459-4466 (1996. 12)

T.Matsumoto、Ahmed Tarek：“通过动态规划（包括线性规划）查找 Petri 网的合法触发序列”Procs.of The 35the IEEE Con​​f.on Decision and Control。

T.Matsumoto: "Finding legal firing sequence in submarking reachability problems of Petri nets by discrete-time Pontryagin′s minimum principle" Proceedings of ISCAS ′97 (IEEE). 1017-1020 (1997. 6)

T. Matsumoto：“通过离散时间 Pontryagin 最小原理查找 Petri 网子标记可达性问题中的合法触发序列”ISCAS 97 论文集 (IEEE) (1997. 6)。

T.Matsumoto: "Generalized submarking reachability problems with/without a firing count vector and their inverse problems of Petri nets" Technical Report of IEICE (CST95-35). Vol.95, No.471. 47-54 (1996. 01)

T.Matsumoto：“带/不带发射计数向量的广义子标记可达性问题及其 Petri 网的逆问题”IEICE 技术报告 (CST95-35)。