Least-cost planning sequence estimation in labelled Petri nets

Abstract

This paper develops a recursive algorithm for estimating the least-cost planning sequence in a manufacturing system that is modelled by a labelled Petri net. We consider a setting where we are given a sequence of labels that represents a sequence of tasks that need to be executed during a manufacturing process, and we assume that each label (task) can potentially be accomplished by a number of different transitions, which represent alternative ways of accomplishing a specific task. The processes via which individual tasks can be accomplished and the interactions among these processes in the given manufacturing system are captured by the structure of the labelled Petri net. Moreover, each transition in this net is associated with a non-negative cost that captures its execution cost (eg, in terms of the amount of workload or power required to execute the transition). Given the sequence of labels (ie, the sequence of tasks that has to be accomplished), we need to identify the transition firing sequence(s) (ie, the sequence(s) of activities) that has (have) the least total cost and accomplishes (accomplish) the desired sequence of tasks while, of course, obeying the constraints imposed by the manufacturing system (ie, the dynamics and structure of the Petri net). We develop a recursive algorithm that finds the least-cost transition firing sequence(s) with complexity that is polynomial in the length of the given sequence of labels (tasks). An example of two parallel working machines is also provided to illustrate how the algorithm can be used to estimate least-cost planning sequences.

Keywords

labelled Petri nets least-cost firing sequences planning sequence estimation.

Get full access to this article

View all access options for this article.

References

Bellman, R.

1957: Dynamic programming. Princeton University Press.

Cassandras, C.G.

and

Lafortune, S.

1999: Introduction to discrete event systems. Springer.

Desrochers, A.A.

and

AI-Jaar, R.Y.

1995: Applications of Petri nets in manufacturing systems: modeling, control, and performance analysis. IEEE Press.

Forney Jr, G.D.

1973: The Viterbi algorithm. Proceedings of the IEEE 61, 268-78.

Kiritsis, D.

Neuendorf, K.-P.

and

Xirouchakis, P.

1999: Petri net techniques for process planning cost estimation . Advances in Engineering Software 30, 375-87.

Lin, S.

Kasami, T.

Fujiwara, T.

and

Fossorier, M.

1998: Trellises and trellis-based decoding algorithms for linear block codes. Kluwer Academic.

Moore, K.E.

Gungor, A.

and

Gupta, S.M.

1998: Disassembly process planning using Petri nets. Proceedings of the 1998 IEEE International Symposium on Electronics and the Environment , 88-93.

Morita, K.

and

Watanabe, T.

1996: The legal firing sequence problem of Petri nets with state machine structure. Proceedings of the 1996 IEEE International Symposium on Circuits and Systems, 64-67.

Murata, T.

1989: Petri nets: properties, analysis and applications. Proceedings of the IEEE 77, 541-80.

10.

Park, J.

and

Reveliotis, S.A.

2001: Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automatic Control 46, 1572-83.

11.

Proth, J.-M.

and

Xie, X.

1996: Petri nets: a tool for design and management of manufacturing systems. John Wiley & Sons.

12.

Rosell, J.

2004: Assembly and task planning using Petri nets: a survey . Journal of Engineering Manufacture 218, 987-94.

13.

Ru, Y.

and

Hadjicostis, C.N.

2006: State estimation in discrete event systems modeled by labeled Petri nets. Proceedings of the 45th IEEE International Conference on Decision and Control, 6022-27.

14.

Sampath, R.

Darabi, H.

Buy, U.

and

Liu, J.

2008: Control reconfiguration of discrete event systems with dynamic control specifications. IEEE Transactions on Automation Science and Engineering 5, 84-100.

15.

Sreenivas, R.S.

1997: On the existence of supervisory policies that enforce liveness in discrete-event dynamic systems modeled by controlled Petri nets . IEEE Transactions on Automatic Control, 42, 928-45.

16.

Tang, Y.

Zhou, M.

and

Caudill, R.J.

2001: An integrated approach to disassembly planning and demanufacturing operation. IEEE Transactions on Robotics and Automation 17, 773-84.

17.

Tang, Y.

Zhou, M.

and

Gao, M.

2006: Fuzzy-Petri-net-based disassembly planning considering human factors. IEEE Transactions on Systems, Man, and Cybernetics-Part A 36, 718-26.

18.

Taoka, S.

and

Watanabe, T.

1999: A linear time algorithm solving the legal firing sequence problem for a class of edge-weighted cactuses. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 893-98.

19.

Viterbi, A.D.

1967: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory IT- 13, 260-69.

20.

Watanabe, T.

2000: The legal firing sequence problem of Petri nets. IEICE Transactions on Information and Systems 3, 397-406.

21.

Wu, N.

and

Zhou, M.

2005: Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. IEEE Transactions on Systems, Man, and Cybernetics-Part B 35, 1193-202.

22.

Zussman, E.

and

Zhou, M.

1999: A methodology for modeling and adaptive planning of disassembly processes. IEEE Transactions on Robotics and Automation 15, 190-94.