Reachability search in timed Petri nets using constraint programming

This paper presents a logical abstraction of the reachability graph of a timed Petri net using constraint programming. We apply it to the scheduling of transient inter-production states for cyclic productions in Flexible Manufacturing system. So, we propose to adapt the approach Benasser and Yim (1999) based on the search of the accessibility by means of constraints using concepts of partial marking and partial step which allow a logical abstraction of the reachability graph of a Petri net. Having the timed Petri net (where a duration is associated to each transition), we propagate time to the obtained steps. In fact, we associate, to each marking extracted from a step, a timestamp vector: each timestamp corresponds to the date of the last token produced in a place at a step. Then, under temporal constraints, we solve scheduling problems, using constraint programming.