Scheduling Flexible Manufacturing Systems with Petri Nets Based on the Cell Enumeration Method

摘要

In the field of modern manufacturing, flexible manufacturing systems (FMS) is very important because it can schedule and optimize multipurpose machines to produce multiple types of products. When applying the FMS technology, Petri Net is used to model the machines, parts and the whole manufacturing progress. The core concern of FMS is to make sure that the manufacturing system can transfer from the original state to the final state, which is called reachabilty. Therefore, reachability analysis is one of the most important problems of FMS. When Petri Net is acyclic, the reachability analysis can be performed by finding a integer solution to a set of linear equation, named fundamental equation, which is known to be NP-complete. In this paper, a novel approach for finding the integer solution is applied by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry to identify firing count vector solution(s) to the fundamental equation on a bounded integer set with a complexity bound of O((nu)n!m), where n is the number of nodes, m is the number of arcs and u is the upper bound of the number of firings for all individual arcs.