Skip to main content
Erschienen in: OR Spectrum 3/2007

01.07.2007 | Regular Article

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

verfasst von: Naiqi Wu, MengChu Zhou

Erschienen in: OR Spectrum | Ausgabe 3/2007

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Coffman EG Jr, Elphick MJ, Shoshani A (1972) System deadlocks. ACM Comput Surv 3(2):67–78CrossRef Coffman EG Jr, Elphick MJ, Shoshani A (1972) System deadlocks. ACM Comput Surv 3(2):67–78CrossRef
Zurück zum Zitat Cormen T, Leiserson C, Rivest R (1994) Introduction to algorithms. McGraw-Hill, New York Cormen T, Leiserson C, Rivest R (1994) Introduction to algorithms. McGraw-Hill, New York
Zurück zum Zitat Fanti MP, Maione B, Mascolo S, Turchiano B (1997) Event-based feedback control for deadlock avoidance in flexible production systems. IEEE Trans Robot Autom 13:347–363CrossRef Fanti MP, Maione B, Mascolo S, Turchiano B (1997) Event-based feedback control for deadlock avoidance in flexible production systems. IEEE Trans Robot Autom 13:347–363CrossRef
Zurück zum Zitat Jeng MD, Chen SC (1998) A heuristic search approach using approximate solutions of Petri net state equations for scheduling flexible manufacturing systems. Int J Flex Manuf Syst 10(2) Jeng MD, Chen SC (1998) A heuristic search approach using approximate solutions of Petri net state equations for scheduling flexible manufacturing systems. Int J Flex Manuf Syst 10(2)
Zurück zum Zitat Johri PK (1993) Practical issues in scheduling and dispatching in semiconductor wafer fabrication. J Manuf Syst 12:74–485CrossRef Johri PK (1993) Practical issues in scheduling and dispatching in semiconductor wafer fabrication. J Manuf Syst 12:74–485CrossRef
Zurück zum Zitat Kim CO, Kim SS (1997) An effective real-time deadlock-free control for automated manufacturing systems. Int J Prod Res 35(6):1545–1560CrossRef Kim CO, Kim SS (1997) An effective real-time deadlock-free control for automated manufacturing systems. Int J Prod Res 35(6):1545–1560CrossRef
Zurück zum Zitat Lawley MA (1999) Deadlock avoidance for production systems with flexible routing. IEEE Trans Robot Autom 15(3):497–509CrossRef Lawley MA (1999) Deadlock avoidance for production systems with flexible routing. IEEE Trans Robot Autom 15(3):497–509CrossRef
Zurück zum Zitat Lawley M, Reveliotis S, Ferreira P (1998) A correct and scalable deadlock avoidance policy for flexible manufacturing systems. IEEE Trans Robot Autom 14:796–809CrossRef Lawley M, Reveliotis S, Ferreira P (1998) A correct and scalable deadlock avoidance policy for flexible manufacturing systems. IEEE Trans Robot Autom 14:796–809CrossRef
Zurück zum Zitat Lee DY, DiCesare F (1994) Scheduling flexible manufacturing system using Petri nets and heuristic search. IEEE Trans Robot Autom 10(2):123–132CrossRef Lee DY, DiCesare F (1994) Scheduling flexible manufacturing system using Petri nets and heuristic search. IEEE Trans Robot Autom 10(2):123–132CrossRef
Zurück zum Zitat Murata T (1989) Petri nets: properties, analysis, and application. Proc IEEE 77:541–579CrossRef Murata T (1989) Petri nets: properties, analysis, and application. Proc IEEE 77:541–579CrossRef
Zurück zum Zitat Reveliotis SA, Ferreira PM (1996) Deadlock avoidance policies for automated manufacturing cells. IEEE Trans Robot Autom 12(6):845–857CrossRef Reveliotis SA, Ferreira PM (1996) Deadlock avoidance policies for automated manufacturing cells. IEEE Trans Robot Autom 12(6):845–857CrossRef
Zurück zum Zitat Reveliotis SA, Lawley M, Ferreira P (1997) Polynomial complexity deadlock avoidance policies for sequential resource allocation systems. IEEE Trans Automat Contr 42:1344–1357CrossRef Reveliotis SA, Lawley M, Ferreira P (1997) Polynomial complexity deadlock avoidance policies for sequential resource allocation systems. IEEE Trans Automat Contr 42:1344–1357CrossRef
Zurück zum Zitat Roszkowska E, Jentink J (1993) Minimal restrictive deadlock avoidance in AMS. In: Proceedings of the 2nd European Control Conference ECC ’93, Groningen, pp 530–534 Roszkowska E, Jentink J (1993) Minimal restrictive deadlock avoidance in AMS. In: Proceedings of the 2nd European Control Conference ECC ’93, Groningen, pp 530–534
Zurück zum Zitat Wu NQ (1997) Avoiding deadlocks in automated manufacturing systems with shared material handling system. In: Proceedings of the 1997 IEEE International Conference on Robotics and Automation, Albuquerque, pp 2427–2433 Wu NQ (1997) Avoiding deadlocks in automated manufacturing systems with shared material handling system. In: Proceedings of the 1997 IEEE International Conference on Robotics and Automation, Albuquerque, pp 2427–2433
Zurück zum Zitat Wu NQ (1999) Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model. IEEE Trans Syst Man Cybern Part C Appl Rev 29(2):192–204CrossRef Wu NQ (1999) Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model. IEEE Trans Syst Man Cybern Part C Appl Rev 29(2):192–204CrossRef
Zurück zum Zitat Wu NQ, Zhou MC (2001) Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems. IEEE Trans Robot Autom 17(5):658–669CrossRef Wu NQ, Zhou MC (2001) Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems. IEEE Trans Robot Autom 17(5):658–669CrossRef
Zurück zum Zitat Wysk RA, Yang NS, Joshi S (1991) Detection of deadlocks in flexible manufacturing cells. IEEE Trans Robot Autom 7(6):853–859CrossRef Wysk RA, Yang NS, Joshi S (1991) Detection of deadlocks in flexible manufacturing cells. IEEE Trans Robot Autom 7(6):853–859CrossRef
Zurück zum Zitat Xing KY, Hu BS, Chen HX (1996) Deadlock avoidance policy for Petri net modeling of flexible manufacturing systems with shared resources. IEEE Trans Automat Contr 41(2):289–295CrossRef Xing KY, Hu BS, Chen HX (1996) Deadlock avoidance policy for Petri net modeling of flexible manufacturing systems with shared resources. IEEE Trans Automat Contr 41(2):289–295CrossRef
Zurück zum Zitat Yoon HJ, Lee DY (2001) Identification of potential deadlock set in semiconductor track systems. In: Proceedings of the 2001 IEEE International Conference on Robotics and Automation, Seoul, 1820–1825 Yoon HJ, Lee DY (2001) Identification of potential deadlock set in semiconductor track systems. In: Proceedings of the 2001 IEEE International Conference on Robotics and Automation, Seoul, 1820–1825
Zurück zum Zitat Yoon HJ, Lee DY (2004) Deadlock-free scheduling of photolithography equipment in semiconductor fabrication. IEEE Trans Semicond Manuf 17(1):42–54CrossRef Yoon HJ, Lee DY (2004) Deadlock-free scheduling of photolithography equipment in semiconductor fabrication. IEEE Trans Semicond Manuf 17(1):42–54CrossRef
Zurück zum Zitat Zhou MC, DiCesare F (1992) A hybrid methodology for synthesis of Petri nets for manufacturing systems. IEEE Trans Robot Autom 18(3):350–361CrossRef Zhou MC, DiCesare F (1992) A hybrid methodology for synthesis of Petri nets for manufacturing systems. IEEE Trans Robot Autom 18(3):350–361CrossRef
Zurück zum Zitat Zhou MC, Venkatesh K (1998) Modeling, simulation and control of flexible manufacturing systems: Petri net approach. World Scientific, Singapore Zhou MC, Venkatesh K (1998) Modeling, simulation and control of flexible manufacturing systems: Petri net approach. World Scientific, Singapore
Metadaten
Titel
Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets
verfasst von
Naiqi Wu
MengChu Zhou
Publikationsdatum
01.07.2007
Verlag
Springer-Verlag
Erschienen in
OR Spectrum / Ausgabe 3/2007
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI
https://doi.org/10.1007/s00291-006-0046-3

Weitere Artikel der Ausgabe 3/2007

OR Spectrum 3/2007 Zur Ausgabe