In: IEICE Transactions, Vol. E74, No. 10, Special Issue on Petri Nets and Discrete Event Systems. October 1991.
Abstract: The subject of the paper is the minimum initial marking problem for scheduling in timed Petri net PN: ``given a vector X of nonnegative integers, a P-invariant Y of PN and a nonnegative integer pi. find an initial marking M minimizing the value tr(y)M among those initial marking M' such that there is a scheduling sigma having the total completion time tau(sigma)<=pi with respect to M', X and PN (a sequence of transitions, with the first transition firable on M', such that every transition t can fire prescribed number X(t) of times)''. The paper shows NP-hardness of the problem and proposes two approximation algorithms with their experimental evaluation.