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+.
展开▼
