A Heuristic Algorithm AADO 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 a heuristic algorithm AAD+ produces the best solutions among existing ones. This paper proposes an algorithm AADO, an improved version of AAD+, by incorporating a new selection rule of transitions to be fired, improving operations of token-addition, and incorporating the algorithm FEIDEQ having the highest capability as one to find firing sequences. It is shown that, through experimental evaluation, the proposed one has higher capability than AAD+. In our experimental evaluation, AADO is applied to 660 test problems: the average total number of tokens in initial markings by AADO is about 3% less than that by AAD+, and the average CPU time by AADO is about 1.2 times that by AAD+.