This paper deals with the problem of estimating the Minimum Initial Marking (MIM) of Labeled Petri Nets (L-PN). By the observation of a sequence of labels, we determine the set of possible MIMs related to a given L-PN through an approach based on GRASP (Greedy Randomized Adaptive Search Procedure) inspired method – GMIM. The objective is to get the maximum of feasible MIMs by exploring the search space and giving best solutions for real time cyber systems in short time. We consider four basic assumptions during the reasoning: (i) the L-PN structure is known; (ii) for each transition of L-PN, a label is associated, (iii) the label sequence is known, and (iv) all transitions of L-PN are observable. We show the validity and efficiency of our approach by applying the proposed GMIM metaheuristic to two validation examples: Initialization of two parallel machines (example widely cited in literature) and resources allocation in a monitoring problem via mobile robot network.
29 September 2012 in The International Journal of Advanced Manufacturing Technology
In this paper, we consider the on-line estimation of current subsequences for Partially Observable P-time Petri Nets and their starting markings on a sliding horizon composed of steps defined by two successive occurrences of observable transition firings. We propose a general strategy composed of two phases: Phase 1 exploits a simplification of the P-time Petri net under the form of a Timed Petri net; considering a candidate count vector and the relevant starting marking proposed at Phase 1, Phase 2 makes a schedulability analysis by building a system of relations which can be represented by an acyclic conflict-free computation graph. The complete approach avoids the generation of sets which is generally time and space consuming, and provides an optimal solution for each subproblem by using efficient standard tools.