Timed Petri-net based formulation and an algorithm for the optimal scheduling of batch plants

• Autorzy: Tianlong Gu , Parisa A. Bahri , Guoyong Cai
• 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

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

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2003
• Tom: 13
• Numer: 4
• Strony: 527-536

Daty

wydano

2003

otrzymano

2003-03-05

poprawiono

2003-08-05

Twórcy

autor

Tianlong Gu

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

autor

Parisa A. Bahri

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

autor

Guoyong Cai

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

Bibliografia

• 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.
• Błażewicz J., Ecker L., Schmidt G. and Węglarz J. (1996): Scheduling Computer and Manufacturing Processes. - Berlin: Springer.
• Carlier J. and Pinson E. (1988): An algorithm for solving the job shop problem. - Manag. Sci., Vol. 35, No. 2 , pp. 164-176.
• Gonnet S. and Chiotti O. (1997): Modelling of the supervisory control system of a multi purpose batch plant. - Comp. Chem. Eng., Vol. 21S, pp. S691-S696.
• Graells M., Espuna A. and Puigjaner L. (1996): Sequencing intermediate products: A practical solution for multi-purpose production scheduling. - Comp. Chem. Eng., Vol. 20S, pp. S1137-S1142.
• 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.
• 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.
• 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.
• 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.
• 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.
• Ku H.M., Rajagopalan D. and Karimi I.A. (1987): Scheduling in batch processes. - Chem. Eng. Prog., Vol. 83, No. 8, pp. 35-45.
• 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.
• 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.
• 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.
• Murata T. (1989): Petri nets: Properties, analysis and applications. - Proc. IEEE, Vol. 77, No. 4, pp. 541-580.
• Nilsson N. (1980): Principles of artificial intelligence.- Palo Alto, CA: Tioga.
• 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.
• Rippin D.W.T. (1993): Batch process systems engineering: A retrospective and prospective review. - Comp. Chem. Eng., Vol. 17S, pp. s1-s13.
• 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.
• 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.
• 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.
• 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.
• Zhou M.C. and Kurapati V. (1999): Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach. -New Jersey: World Scientific.