The Minimum Initial Marking Problem for Scheduling in Timed Petri Nets

Toshimasa WATANABE  Takenobu TANIDA  Masahiro YAMAUCHI  Kenji ONAGA  

Publication
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: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Application of Petri Nets to Concurrent System Design)
Category: 
Keyword: 
timed Petri nets,  scheduling,  approximation algorithms,  time complexity,  NP-hardness,  

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




Summary: 
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.