Timed Petri-Net Based Formulation and an Algorithm for the Optimal Scheduling of Batch Plants

• Autorzy: Gu T. , Bahri P. A. , Cai G.
• Języki publikacji: EN

Abstrakty

EN

The effective scheduling of operations in batch plants has a great potential for high economic returns, in which the formulation and an optimal solution algorithm are the main issues of study. Petri nets have proven to be a promising technique for solving many difficult problems associated with the modelling, formal analysis, design and coordination control of discrete-event systems. One of the major advantages of using a Petri-net model is that the same model can be used for the analysis of behavioural properties and performance evaluation, as well as for the systematic construction of discrete-event simulators and controllers. This paper aims at presenting a Petri-net based approach to the scheduling of operations in batch plants. Firstly, the short term of the `scheduling of batch plants' is formulated by means of a timed Petri net which can accommodate various intermediate storage policies, such as unlimited intermediate storage (UIS), no intermediate storage (NIS), finite intermediate storage (FIS), and mixed intermediate storage (MIS). Secondly, a heuristic search algorithm for the optimal scheduling of batch plants is given, which is based on generating and checking the markings in the reachability tree of the Petri-net model. Finally, the novel formulation and algorithm are tested with several simulation case studies.

Słowa kluczowe

EN

timed Petri nets; scheduling; batch plants; discrete event; algorithm; heuristic

PL

sieć petriego czasowa; zakład wsadowy; zdarzenie dyskretne

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2003
• Tom: Vol. 13, no 4
• Strony: 527--536
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Gu T.

• School of Computer Science, Guilin University of Electronic Technology, Guilin 541004, China

autor

Bahri P. A.

• School of Engineering, Murdoch University, Murdoch, WA 6150, Australia

autor

Cai G.

• School of Computer Science, Guilin University of Electronic Technology, Guilin 541004, China

Bibliografia

• [1] Adams J., Balas E. and Zawack D. (1988): The shifting bottleneck procedure for job shop scheduling. — Manag. Sci., Vol. 34, No. 3, pp. 391–410.
• [2] Błażewicz J., Ecker L., Schmidt G. and Węglarz J. (1996): Scheduling Computer and Manufacturing Processes. — Berlin: Springer.
• [3] Carlier J. and Pinson E. (1988): An algorithm for solving the job shop problem. — Manag. Sci., Vol. 35, No. 2 , pp. 164–176.
• [4] Gonnet S. and Chiotti O. (1997): Modelling of the supervisory control system of a multipurpose batch plant. — Comp. Chem. Eng., Vol. 21S, pp. S691–S696.
• [5] Graells M., Espuna A. and Puigjaner L. (1996): Sequencing intermediate products: A practical solution for multipurpose production scheduling. — Comp. Chem. Eng., Vol. 20S, pp. S1137–S1142.
• [6] Gu T. and Bahri P.A. (1999): Timed Petri-net representation for short term scheduling of multiproduct batch plants. — Proc. Amer. Contr. Conf., San Diego, USA, pp. 4092–4096.
• [7] Gu T. and Bahri P.A. (2002): A survey of Petri-net applications in batch processes. —Comp. Ind., Vol. 47, No. 1, pp. 99–111.
• [8] Hanisch H.M. (1992): Coordination control modelling in batch production systems by means of Petri nets. — Comp. Chem. Eng., Vol. 16, No. 1, pp. 1–10.
• [9] Jung T.H., Kim M. and Lee I. (1996): Optimal scheduling of multi-product batch processes for various intermediate storage policies.—Ind. Eng. Chem. Res., Vol. 35, No. 11, pp. 4058–4066.
• [10] Kobayashi S., Ono I. and Yamamura M. (1995): An efficient genetic algorithm for job shop scheduling problems. — Proc. 6-th Int. Conf. Genetic Algorithms, Tokyo, Japan, pp. 506–511.
• [11] Ku H.M., Rajagopalan D. and Karimi I.A. (1987): Scheduling in batch processes. — Chem. Eng. Prog., Vol. 83, No. 8, pp. 35–45.
• [12] Ku H.M. and Karimi I.A. (1990): Completion time algorithms for serial multi-product batch processes with shared storage. — Comp. Chem. Eng., Vol. 14, No. 1, pp. 49–56.
• [13] Lee D.Y. and Dicesare F. (1994): Scheduling flexible manufacturing systems using Petri nets and heuristic search. — IEEE Trans. Robot. Automat., Vol. 10, No. 2, pp. 123–132.
• [14] Moro A.R., Yu H. and Kelleher G. (2002): Hybrid heuristic search for the scheduling of flexible manufacturing systems using Petri nets. — IEEE Trans. Robotics and Automation, Vol. 18, No. 2, pp. 240–245.
• [15] Murata T. (1989): Petri nets: Properties, analysis and applications.— Proc. IEEE, Vol. 77, No. 4, pp. 541–580.
• [16] Nilsson N. (1980): Principles of artificial intelligence. — Palo Alto, CA: Tioga.
• [17] Papageorgaki S. and Reklaitis G.V. (1990): Optimal design of multi-purpose batch plants, I: Problem formulation. — Ind. Eng. Chem. Res., Vol. 29, No. 5, pp. 2054–2062.
• [18] Rippin D.W.T. (1993): Batch process systems engineering: A retrospective and prospective review. — Comp. Chem. Eng., Vol. 17S, pp. s1–s13.
• [19] Sanmarti E., Friedler F. and Puigjaner L. (1998): Combinatorial technique for short-term scheduling of multi-purpose batch plants based on schedule-graph representation. — Comp. Chem. Eng., Vol. 22S, pp. S847–S850.
• [20] Yamalidou E.C. and Kantor J.C. (1991): Modelling and optimal control of discrete-event chemical processes using Petri nets.—Comp. Chem. Eng., Vol. 15, No. 7, pp. 503–519.
• [21] YoungWoo K., Inaba A., Suzuki T. and Okuma S. (2001a): FMS scheduling based on Petri net model. — Proc. IEEE Int. Symp. Assembly and Task Planning, Fukuoka, Japan, pp. 238–243.
• [22] YoungWoo K., Inaba A., Suzuki T. and Okuma S. (2001b): FMS scheduling based on timed Petri net model and RTA_ algorithm.— Proc. IEEE Int. Symp. Assembly and Task Planning, pp. 848–853.
• [23] Zhou M.C. and Kurapati V. (1999): Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach.—New Jersey: World Scientific.