The Minimum Initial Marking Problem for Scheduling in Timed Petri Nets

Toshimasa WATANABE  Takenobu TANIDA  Masahiro YAMAUCHI  Kenji ONAGA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.10   pp.1407-1421
Publication Date: 1992/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Application of Petri Nets to Concurrent System Design)
timed Petri nets,  scheduling,  approximation algorithms,  time complexity,  NP-hardness,  

Full Text: PDF(1.1MB)>>
Buy this Article

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 π, find an initial marking M minimizing the value YtrM among those initial marking M such that there is a scheduling σ having the total completion time τ(σ)π with respect 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.