|Table of Contents|

Optimal Scheduling of Flexible Manufacturing System Based on Petri Net and Dynamic Weighting Heuristic Strategy


Research Field:
Publishing date:


Optimal Scheduling of Flexible Manufacturing System Based on Petri Net and Dynamic Weighting Heuristic Strategy
HUANG BoZHAO Chun-xiaSUN Ya-min
School of Computer Science and Technology,NUST,Nanjing 210094,China
flexible manufacturing system Petri net scheduling algorithm heuristic function
To improve the efficiency of scheduling of flexible manufacturing system(FMS) based on Petri net,an optimal scheduling algorithm is developed.It adopts an improved method for selecting the optimal nodes to improve the search ability of nodes.In the search process,dynamic weighting heuristic function is used to ensure that the optimal or sub-optimal solution is to be found.The algorithm also adopts a relaxed algorithm which combines A* algorithm and depth first algorithm to accelerate the convergence speed of the algorithm.They can reduce the number of the nodes considered in the search process of reachability graph and quicken the convergence speed.Moreover,the quality of the search result is controllable.The effect of the algorithm is proved by the experiment made in the paper.


[ 1] ?? Xu G, Wu Z M. Dead lock- free scheduling m e thod using Petr i net mode l analysis and GA search[ A ]. The 2002 Interna tiona l Confe rence on Control Applications [ C] . G lasgow, Sco tland: IEEE, 2002: 1153- 1158.
[ 2] Xu G, W u ZM. Dead lock- free schedu ling strategy fo r automa ted production ce ll[ J]. IEEE T ransactions on System s, M an and Cybernetics, Part A, 2004, 34( 1): 113- 122.
[ 3] Lin S Y, Fu L C, Ch iang T C, et a.l Co lored tim ed Pe tr-i net and GA based approach to m ode ling and schedu ling fo rw afer probe center[ A]. The 2003 IEEE Interna tiona l Con ference on Robo tics and Au tom atio [ C] . Ta ipe,i China: IEEE, 2003: 1434- 1439. [ 4 ] Sh ih H, Sekiguchi T. A tim ed Pe tri net and beam search based on- line FM S schedu ling system s w ith routing flex ib ility[ A] . IEEE International Con ference on Robotics and Autom ation[ C ]. Sac ramento, USA: IEEE, 1991: 2548- 2553. [ 5 ] Lee D Y, D iCesare F. FM S scheduling us ing Petr i nets and heur istic search [ J] . IEEE T ransactions on Robo tics and Autom ation, 1994, 10( 2): 123- 132.
[ 6] X iongH H, Zhou M C. Scheduling o f sem iconduc to r test fac ility v ia Petri nets and hybr id heuristic sea rch [ J]. IEEE Transactions on Sem iconductor M anu factu ring, 1998, 11( 3): 384- 393.
[ 7] 薛雷, 郝跃. 面向集成电路制造的基于Petri网的生 产调度[ J] . 电子学报, 2001, 29( 8) : 1064- 1067.
[ 8] Yu H, Reyes A, Cang S, et a.l Com bined Pe tri net m ode ling and A I based heuristic hybrid search for flexiblem anufactur ing system s?? Part I Petri net m ode ling and heur istic search [ J]. Journal of Computers & Industr ia l Eng ineer ing, 2003, 44( 4): 527- 543.
[ 9] H uang Bo, Sun Yu, Sun Y a-m in. Scheduling of flex-i b le m anu factu ring system s based on Pe tr i nets and hybr id heuristic sea rch[ J]. Inte rna tiona l Journa l of Produc tion Resea rch, 2008, 46( 16): 4553- 4565.
[ 10] Pea rl J. H eur istics: inte lligent search strateg ies fo r computer problem so lving [M ]. USA: Add ison-W esley, 1984.


Last Update: 2012-11-02