An Algorithm RADQ* for Finding Legal Firing Sequences of Petri Nets based on Transition Firing Inhibition

摘要

The paper proposes a heuristic algorithm RADQ* for the Maximum Legal Firing Sequence problem of Petri nets (MAX LFS for short) and evaluates it experimentally. RADQ* is improved from the existing one FSDC for MAX LFS by focusing on extended quasi-bottlenecks, and by repeatedly executing the procedures DEADLOCK_COMP, QUASI_BOTTLENECK and EX_QUASI_BOTTLENECK. As experimental evaluation, RADQ* (k = 2) is applied to 1000 test problems to each of which existence of an exact solution is guaranteed, and it has produced an optimum solution to each of 770(77.0%) test problems, showing about 11% improvement from FSDC.