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

Abstract:

In the field of modern manufacturing, flexible manufacturing systems (FMS) is very important because it can scheduleand 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.

• Periodical: Advanced Materials Research (Volume 346)
• Pages: 412-418
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.346.412
• Online since: September 2011
• Authors: Shen Shen Gu

References

[1] Zurawski, R. and Zhou, M.C. (1994). Petri nets and industrial applications: A tutorial. IEEE Transactions on Industrial Electronics, 41, 567–583.

DOI: 10.1109/41.334574

[2] Sun, X.L., Liu, C.L., Li, D., and Gao, J.J. (2008). On duality gap in binary quadratic optimization. In Working paper series. Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong.

[3] Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons, New York.

[4] Kostin, A.E. (2003). Reachability analysis in t-invariant-less petri nets. IEEE Transactions on Automatic Control, 48, 1019–1024.

DOI: 10.1109/tac.2003.812788

[5] Murata, T. (1977). State equation, controllability, and maximal matchings of petri nets. IEEE Transactions on Automatic Control, 22, 412–416.

DOI: 10.1109/tac.1977.1101509

[6] Matsumoto, T., Takata, M., and Moro, S. (2002). Reachability analyses in petri nets by groebner bases. In Proceeding of SICE 2002, 841–846.

DOI: 10.1109/sice.2002.1195268

[7] Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons, New York.

[8] G. L. Nemhauser and L. A. Wolsey. (1988). Integer and Combinatorial Optimization. John Wiley & Sons, New York.

[9] D. Li and X. L. Sun. (2006). Nonlinear Integer Programming. Springer, New York.

[10] Duan Li, Xiaoling Sun, Jianjun Gao, Shenshen Gu, Xiaojin Zheng, (2009).

[11] Matsumoto, T., Takata, M., and Moro, S. (2002). Reachability analyses in petri nets by groebner bases. In Proceeding of SICE 2002, 841–846.

DOI: 10.1109/sice.2002.1195268

[12] Edelsbrunner, H. (1987). Algorithms in Combinatorial Geometry. Springer.

[13] N. Sleumer. (1999). Output-Sensitive Cell Enumeration in Hyperplane Arrangements. Nordic Journal of Computing, 6: 137–161.

[14] T. Zaslavsky. (1975). Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Amer. Math. Soc, 1: 1–101.

DOI: 10.1090/memo/0154