For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1992/10/25
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)>>
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 Ytr・M 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.