Fast Heuristic Algorithms based on Avoiding Occurrence of Behavioral Deadlocks for Minimizing Initial Markings of Petri Nets

摘要

In this paper we consider the minimum initial marking problem (MIM) of Petri nets, one of optimum initial resource allocation problems for variable systems. MIM is known to be NP-hard, and some heuristic algorithms have been proposed. It is shown through computational experiments that (1) a heuristic algorithm AAD has the highest capability among existing ones and requires too much computation time to be practical as the data sizes become huge; (2) AMIM+has the second highest capability and produces a heuristic solution very fast even if the data size is too large. Then this paper proposes improved algorithms of AMIM+ and shows that, thorugh experimental evaluation, the proposed ones have higher capability than AMIM+.