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

Tianlong Gu; Parisa Bahri; Guoyong Cai

International Journal of Applied Mathematics and Computer Science (2003)

  • Volume: 13, Issue: 4, page 527-536
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Gu, Tianlong, Bahri, Parisa, and Cai, Guoyong. "Timed Petri-net based formulation and an algorithm for the optimal scheduling of batch plants." International Journal of Applied Mathematics and Computer Science 13.4 (2003): 527-536. <http://eudml.org/doc/207665>.

@article{Gu2003,
abstract = {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.},
author = {Gu, Tianlong, Bahri, Parisa, Cai, Guoyong},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {scheduling; algorithm; heuristic; discrete event; timed Petri nets; batch plants; Petri net models; reachability tree; optimal tracing},
language = {eng},
number = {4},
pages = {527-536},
title = {Timed Petri-net based formulation and an algorithm for the optimal scheduling of batch plants},
url = {http://eudml.org/doc/207665},
volume = {13},
year = {2003},
}

TY - JOUR
AU - Gu, Tianlong
AU - Bahri, Parisa
AU - Cai, Guoyong
TI - Timed Petri-net based formulation and an algorithm for the optimal scheduling of batch plants
JO - International Journal of Applied Mathematics and Computer Science
PY - 2003
VL - 13
IS - 4
SP - 527
EP - 536
AB - 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.
LA - eng
KW - scheduling; algorithm; heuristic; discrete event; timed Petri nets; batch plants; Petri net models; reachability tree; optimal tracing
UR - http://eudml.org/doc/207665
ER -

References

top
  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. Zbl0637.90051
  2. Błażewicz J., Ecker L., Schmidt G. and Węglarz J. (1996): Scheduling Computer and Manufacturing Processes. - Berlin: Springer. Zbl0911.90201
  3. Carlier J. and Pinson E. (1988): An algorithm for solving the job shop problem. - Manag. Sci., Vol. 35, No. 2 , pp. 164-176. Zbl0677.90036
  4. 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. 
  5. 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. 
  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. Zbl0422.68039
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.