A PETRI NET APPROACH FOR SOLVING SIMPLE ASSEMBLY LINE BALANCING PROBLEM

Abstract

Assembly line balancing problem is an assignment problem. Tasks are assigned to work stations on the line by providing the precedence relations between tasks. When the only one product is produced on the line and its tasks have deterministic times, the problem is called simple assembly line balancing problem (SALBP). If number of work stations on the line is fixed, then cycle time should be reduced (SALBP-1). Heuristics based on branch and bound procedures, tabu search metaheuristics, genetic approaches, and etc. have been developed to solve SALBP-1. In this article, Petri nets are represented as a new approach to solve this problem. Petri nets are mathematical and graphical tool to model, design, and analyze discrete event systems. Proposed algorithm based on Petri nets uses the especially reachability analysis to determine available tasks and select task into them. Algorithm is coded in MATLAB 6.0. Proposed algorithm is tested on Tonge’s 70-tasks problem, and then results are compared with existing seven methods’ results. The algorithm gave best results for 12 of 13 cycle time

Keywords

• Assembly line balancing problem, Petri nets, Assembly production, Reachability analysis

BASİT MONTAJ HATTI DENGELEME PROBLEMİ ÇÖZÜMÜ İÇİN BİR PETRİ AĞI YAKLAŞIMI

Abstract

Montaj hattı dengeleme problemi bir atama problemidir. İş elemanları, hat üzerindeki iş istasyonlarına birbirleri arasındaki öncelik ilişkileri sağlanarak atanırlar. Hat üzerinde sadece bir ürün işleniyorsa ve bu ürüne ait iş elemanlarının süreleri biliniyor ve sabit ise problem, basit montaj hattı dengeleme problemi olarak adlandırılır. Eğer hat üzerindeki iş istasyonu sayısı belli ise çevrim süresi azaltılmalıdır (BMHDP-1). BMHDP-1’i çözmek için Dal & Sınır algoritmaları, tabu araştırması, genetik algoritmalar vb. Araştırma tekniklerine dayalı sezgisel yöntemler geliştirilmektedir. Bu makalede, bu problemin çözümü için yeni bir yaklaşım olarak Petri ağları sunulmuştur. Petri ağları, kesikli olaylı sistemleri modelleyen, tasarlayan ve analiz eden bir tekniktir. Önerilen Petri ağlarına dayalı algoritma özellikle ulaşılabilirlik analizini kullanır. Algoritma MATLAB 6.0’da kodlanmıştır. Önerilen algoritmanın testi, Tonge’nin 70 iş elemanlı probleminde yapılmış, sonuçlar mevcut yedi yöntemin sonuçları ile karşılaştırılmıştır. Algoritma, 13 çevrim süresinin 12’sinde en iyi sonuçları vermiştir

Keywords

• Montaj hattı dengeleme problemi, Petri ağları, Montaj üretim, Ulaşılabilirlik analizi

References

1. Adamou M., Zerhoni S.N., Bourjault A. (1998): “Hierarchical Modeling and Control of Flexible Assembly Systems Using Object-oriented Petri Nets”, International Journal of Computer Integrated Manufacturing. Vol. 11, No. 1, pp. 18-33.
2. Bautista J., Suarez R., Mateo M., Companys R. (2000): “Local Search Heuristics for Assembly Lien Balancing Problem with Incompatibilities between Tasks”, Proceedings of the 2000 IEEE International Conference on Robotics & Automation, San Francisco, CA., pp. 2404-2409.
3. Baybars I. (1986b): “A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem”, Management Science, Vol. 32, No. 8, pp. 909-932.
4. Baybars I. (1986a): “An Efficient Heuristic Method for the Simple Assembly Line Balancing Problem”, International Journal of Production Research, Vol. 24, No. 1, pp. 149-166.
5. Cao T., Sanderson A.C. (1994): “Task Decomposition and Analysis of Robotic Assembly Task Plans Using Petri Nets”, IEEE Transactions on Industrial Electronics, Vol. 41, No.6, pp. 620-629.
6. Chiang W.C. (1998): “The Application of a Tabu search Metaheuristic to the Assembly Line Balancing Problem”, Annals of Operations Research, No. 77, pp. 209-227.
7. D’Souza K.A., Khator S.K. (1997): “System Reconfiguration to Avoid Deadlocks in Automated Manufacturing Systems”, Computers Industrial Engineering, Vol. 32, No.2. pp 455-465.
8. Desrochers A.A., Al-Jaar R.Y. (1995): “Applications of Petri Nets in Manufacturing Systems, Modeling, Control, and Performance Analysis”, IEEE Press, New York.

9. Erel E., Sarin S.C. (1998): “A Survey of the Assembly Line Balancing Procedures”, Production Planning and Control, Vol. 9, No. 5, pp. 414-434.
10. Frey G. (2000): “Assembly Line Sequencing based on Petri Net T-Invariants”, Control Engineering Practice, Vol. 8, pp. 63-69
11. Hoffmann T.R. (1992): “EUREKA: A Hybrid System for Assembly Line Balancing”, Management Science, Vol. 38, pp. 39-47
12. Jeng M.D. (1997): “Petri Nets for Modeling Automated Manufacturing Systems with Error Recovery”, IEEE Transaction on Robotics and Automation, Vol. 13, No. 5, pp. 752-760.
13. Johnson R.V. (1988): “Optimally Balancing Large Assembly Lines with FABLE”, Management Science, Vol. 34, No. 2, pp. 240-253.
14. Kılınçcı Ö. (2003): “Simple Assembly Line Balancing Problem: A Petri Net Approach”, Doktora Tezi, İzmir, Dokuz Eylül Üniversitesi, Fen Bilimleri Enstitüsü.
15. Kim Y.K., Kim Y.J., Kim Y. (1996): “Genetic Algorithms for Assembly Line Balancing with various Objectives”, Computers and Industrial Engineering, Vol. 30, No. 3, pp. 397-409.
16. McCarragher B.J. (1994): “Petri Net Modeling for Robotic Assembly and Trajectory Planning”, IEEE Transactions on Industrial Electronics, Vol. 41, No. 6, pp. 631-640.
17. Moore K.E., Güngör A., Gupta S.M. (2001): “Petri Net Approach to Disassembly Process Planning for Products with Complex AND/OR Precedence Relationships”, European Journal of Operational Research, Vol. 135, pp. 428-449.
18. Murata T. (1989): “Petri Nets: Properties, Analysis and Applications”, Proceedings of IEEE, Vol. 77, No. 4, pp. 541-580.
19. Nourie F.J., Venta E.R. (1991): “Finding the Optimal Line Balances with OptPack”, Operations Research Letters, Vol. 10, pp. 165-171.
20. Ramaswamy S., Valavanis K.P., Barber S. (1997): “Petri Net Extensions for the Development of MIMO Net Models of Automated Manufacturing Systems”, Journal of Manufacturing Systems, Vol. 16, No. 3, pp. 175-191.
21. Rubinovitz J., Levitin G. (1995): “Genetic Algorithm for Assembly Line Balancing”, International Journal of Production Economics, Vol. 41, pp. 343-354.
22. Sabuncuoğlu I., Erel E., Tanyer M. (2000): “Assembly Line Balancing Using Genetic Algorithms”, Journal of Intelligent Manufacturing, No. 11, pp. 295-310.
23. Scholl A., Klein R. (1997): “SALOME: A Bidirectional Branch-and-bound Procedure for Assembly Line Balancing”, INFORMS Journal on Computing, Vol. 9, No. 4, pp. 319-334.
24. Scholl A., Voss S. (1996): “Simple Assembly Line Balancing-heuristic Approaches”, Journal of Heuristics, No. 2, pp. 217-244.
25. Sprecher A. (1999): “A Competitive Branch-and-bound algorithm for the Simple Assembly Line Balancing Problem”, International Journal of Production Research, Vol. 37, No. 8, pp. 1787-1816.
26. Teng S.H., Zhang J. (1993): “A Petri Net-based Decomposition Approach in Modeling of Manufacturing Systems”, International Journal of Production Research, Vol. 31, No. 6, pp. 1423-1439.
27. Zha X.F., Lim S.Y.E., Fok S.C. (1998): “Integrated Knowledge-based Petri Net Intelligent Flexible Assembly Planning”, Journal of Intelligent Manufacturing, Vol. 9, pp. 235-250.