Finding Legal Firing Sequences of Timed Petri Nets Based on Postponing Firing Activity of Transitions

摘要

The Timed Petri Net Maximum Scheduling Problem (MAX TPS for short) is defined as follows: "Given a timed Petri net TPN, an initial marking M and a firing count vector X, find a firing sequence δ satisfying the following (i) through (iii): (i) δ is legal on M with respect to some X' ≤ X; (ii) the length |δ| of δ is maximum among those sequences satisfying (i), (iii) the completion time τ(δ) of δ is minimum among those satisfying (ii), where X' ≤ X means that X'(t) ≤ X(t) for any t ε T." This paper proposes a heuristic algorithm SDS2_pdc and shows, through computational experiment, that its capability is the highest among existing ones.