Engineering efficiency unleashed: minimum initial marking estimation in labeled Petri nets through a cutting-edge hybrid evolutionary heuristic

Abstract

Purpose As widely used by the design and decision-making of resource allocation and communications in manufacturing, monitoring of mobile robot network and other engineering fields, minimum initial marking (MIM) estimation is to determine the initial marking(s) with a minimum total number of tokens in labeled Petri net models of real-world application systems in engineering. This paper addresses the MIM estimation under the observation of a label sequence. We aim to find all possible solutions while reducing the computational cost in solving this NP-hard problem by a hybrid evolutionary heuristic. Design/methodology/approach First, a set of transition firing sequences (TFSs) consistent with the observed label sequences is found to generate the initial population of the genetic algorithm (GA). Second, we calculate the initial markings that correspond to each TFS and are minimal, and the quality of individuals is assessed. Third, simulated annealing (SA) is used to improve the individuals in the population, and then GA is used for a global search. Finally, the above operations are repeated until the termination condition is satisfied. Findings In comparison with the existing methods for finding MIMs with heuristic algorithms, our algorithm improves 51.5–316.7% in the number of obtained MIMs. Moreover, the computation time is reduced by 90.1% compared with a classical algorithm. Originality/value In this paper, an effective evolutionary algorithm by hybridizing GA and SA is developed to estimate MIMs. The proposed approach can obtain the complete MIM set at a lower computational cost.