An improved heuristic algorithm FEIDEQ for the maximum legal firing sequence problem of Petri nets
An improved heuristic algorithm FEIDEQ for the maximum legal firing sequence problem of Petri nets
复制标题
DOI：
10.1109/iscas.2006.1693625
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
Satoru Shimada;Satoshi Taoka;M. Yamauchi;Toshimasa Watanabe
中科院分区：
文献类型：
--
作者：
Satoru Shimada;Satoshi Taoka;M. Yamauchi;Toshimasa Watanabe
针对Petri网最大合法触发序列问题，提出一种启发式算法FEIDEQ（简称MAX LFS），并根据实验结果对其进行评估。 FEIDEQ 是在 FSDC 的基础上进行改进的，FSDC 被认为是现有技术中能力最高的，它加入了新的转换选择规则。在我们的实验评估中，FEIDEQ 应用于 2540 个测试问题，并且对于其中的 2040 个测试问题，保证存在最优解。在这 2040 个测试问题中，FEIDEQ 对 1864 个（91.3%）测试问题中的每一个都给出了最优解，其结果约为 FSDC 的 2.57 倍，是迄今为止最好的。此外，通过采用改进的回溯，平均CPU时间约为通用网络FSDC的0.86倍
The paper proposes a heuristic algorithm FEIDEQ for the maximum legal firing sequence problem of Petri nets (MAX LFS for short) and evaluates it based on experimental results. FEIDEQ is improved from FSDC that has been known to have the highest capability among the existing ones, by incorporating a new selection rule of transitions. In our experimental evaluation, FEIDEQ is applied to 2540 test problems, and, for each of 2040 of them, existence of an optimum solution is guaranteed. Among these 2040 test problems, FEIDEQ has produced an optimum solution to each of 1864 (91.3%) test problems, showing about 2.57 times that of FSDC, the best one so far. Furthermore, by adopting improved backtracking, average CPU time is about 0.86 times that of FSDC for general nets