Paper Info
Title
A petri net-based modeling and scheduling with a branch and bound algorithm
Abstract
We examine a non-cyclic scheduling problem of a timed Petri net (TPN) with a branch and bound (B&B) algorithm. There have been many approaches and algorithms for conventional scheduling problems such as job shops, resource-constrained project scheduling problems (RCPSPs), and robotized system scheduling problems. Most of these methods have focused on their effectiveness or efficiency in solving their own problems. However, they tend to ignore the issue of compatibility with other scheduling problems and the solution methods are ad hoc and hard to be used for other scheduling problems with even small changes. Petri nets have been widely used for modeling and analyzing complex discrete event dynamic systems, such as robotized manufacturing cells or other automated manufacturing systems. There are studies on scheduling cyclic Petri net models and some non-cyclic Petri net models for specific applications. In this paper, we examine a scheduling problem for non-cyclic TPNs, where there is the starting and end transitions, and the transitions do not repeat an identical firing cycle. We also allow multiple arc weights in TPNs so as to model batch processing of tasks at a resource and multiple units of a resource required for a task. We briefly explain how various scheduling constraints and objectives can be modeled by TPNs. Then, we develop an efficient B&B procedure that utilizes a dynamic branching strategy and a resource-based lower bound. We finally present examples of the B&B algorithm for an RCPSP and a single-armed cluser tool scheduling problem.
Year
DOI
Venue
2012
10.1109/ICSMC.2012.6377995
SMC
Keywords
Field
DocType
non-cyclic scheduling,dynamic branching strategy,scheduling,batch processing,petri net-based modeling,petri nets,discrete event systems,tree searching,branch and bound algorithm,timed petri net,petri net-based scheduling,single-armed cluser tool scheduling problem,noncyclic scheduling problem,complex discrete event dynamic system,scheduling constraint,resource-based lower bound,tpn,robots
Fair-share scheduling,Computer science,Flow shop scheduling,Two-level scheduling,Stochastic Petri net,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Round-robin scheduling,Distributed computing
Conference
ISSN
ISBN
Citations 
1062-922X
978-1-4673-1712-2
4
PageRank 
References 
Authors
0.41
11
3
Name
Order
Citations
PageRank
Hyun-Jung Kim1442.37
Jun-Ho Lee222421.56
Tae-Eog Lee328530.02