Minimum initial marking estimation in labeled petri nets

Abstract

This technical note develops algorithms for estimating the minimum initial marking(s) following the observation of a sequence of labels produced by underlying transition activity in a known labeled Petri net (PN). Since multiple (generally, infinite) initial markings are possible, we focus on obtaining the set of minimum initial markings of the net, i.e., the initial markings that (i) allow for the firing of at least one sequence of transitions that is consistent with both the observed sequence of labels and the net structure; and (ii) have the least total number of tokens (i.e., the minimum total number of tokens when summed over all places). We develop a recursive algorithm that is able to find the minimum initial marking(s) with complexity that is polynomial in the length of the observed label sequence; we also discuss heuristics that can further reduce complexity at the cost of obtaining a subset or an approximation of the minimum initial markings. An example of minimum initial marking estimation for a PN model of two machines working in parallel is also provided to illustrate how the proposed algorithm and heuristics can be used to determine the minimum number of resources needed at initialization to execute a specified sequence of tasks. © 2012 IEEE.