A Heuristic Algorithm FSDC Based on Avoidance of Deadlock Components in Finding Legal Firing Sequences of Petri Nets

説明

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.

詳細情報 詳細情報について

問題の指摘

ページトップへ