In: Proceedings of the 24th International Conference on Applications and Theory of Petri Nets (ICATPN 2003), Eindhoven, The Netherlands, June 23-27, 2003, pages 417-439. Volume 2679 of Lecture Notes in Computer Science / Wil M. P. van der Aalst and Eike Best (Eds.) --- Springer-Verlag, June 2003.
Abstract: The paper proposes a heuristic algorithm FSDC for solving the Maximum Legal Firing Sequence problem of Petri nets ( MAX LFS for short) and evaluates it experimentally. FSDC is improved from the existing one FSD for MAX LFS by focusing on deadlock components, instead of D-siphons, and by incorporating efficient backtracking. As experimental evaluation, FSDC is applied to 3017 test problems to each of which existence of an exact solution is guaranteed, and it has produced an optimum solution to each of 2330 (77.2%) test problems, which is about 1.43 times more than that of FSD, while the average CPU time is about 1.82 times longer than that of FSD. For five related problems each of which contains MAX LFS as a subproblem, it is experimentally shown that incorporating FSDC for solving MAX LFS gives us five heuristic algorithms that are superior in capability to existing ones.
Keywords: Analysis and synthesis; structure and behavior of nets.