Search results for: reachability graph
2 Applying Branch-and-Bound and Petri Net Methods in Solving the Two-Sided Assembly Line Balancing Problem
This paper combines the branch-and-bound method and the petri net to solve the two-sided assembly line balancing problem, thus facilitating effective branching and pruning of tasks. By integrating features of the petri net, such as reachability graph and incidence matrix, the propose method can support the branch-and-bound to effectively reduce poor branches with systematic graphs. Test results suggest that using petri net in the branching process can effectively guide the system trigger process, and thus, lead to consistent results.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1584
1 A Technique for Reachability Graph Generation for the Petri Net Models of Parallel Processes
Abstract:Reachability graph (RG) generation suffers from the problem of exponential space and time complexity. To alleviate the more critical problem of time complexity, this paper presents the new approach for RG generation for the Petri net (PN) models of parallel processes. Independent RGs for each parallel process in the PN structure are generated in parallel and cross-product of these RGs turns into the exhaustive state space from which the RG of given parallel system is determined. The complexity analysis of the presented algorithm illuminates significant decrease in the time complexity cost of RG generation. The proposed technique is applicable to parallel programs having multiple threads with the synchronization problem. Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1589