The paper proposes a heuristic algorithm FSDB for the Maximum Legal Firing Sequence problem of Petri nets (MAX LFS for short) and evaluates it experimentally. FSDB is an improved version of the existing one FSD for LFS backtracking operation is incorporated. As experimental evaluation, FSDB is applied to 2495 test problems to each of which existence of an exact solution is guaranteed, and it has produced an optimum solution to each of 1621(65.0) test problems, showing about 8 improvement from FSD. Furthermore, for five related problems each of which contains MAX LFS as a subproblem, we propose five heuristic algorithms in which MAX LFS is to he solved by FSDB. It is experimentally shown that capability of these algorithms is superior to existing ones.
展开▼
