ترکیب الگوریتم پرواز پرندگان و الگوریتم ابتکاری CUL برای حل مسأله برش دو بعدی غیرگیوتینی با تقاضا

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشجوی کارشناسی ارشد.

2 استادیار، دانشگاه یزد.

چکیده

در این مقاله، مسأله برش دو بعدی با تقاضا مورد بررسی قرار میگیرد. در این مسأله با برش ورقهای مستطیل شکل بزرگ، مستطیل های کوچکتر مورد نیاز باید به نحوی تولید شوند که ضمن تأمین تقاضا برای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شود. مسأله برش، جزء مسائل NP-Hard است که روشهای دقیق قادر، به حل عملی آنها نیستند. لذا در این مقاله با استفاده از الگوریتم پرواز پرندگان، الگوریتمی فراابتکاری برای حل مسأله برش دو بعدی با تقاضا ارائه شده است. برای بهبود کارایی این الگوریتم و جلوگیری از همپوشانی در مسأله برش، الگوریتم ابتکاری CUL به کار گرفته شد. همچنین برای بررسی نتایج الگوریتم پیشنهادی )ترکیب الگوریتم های PSO و CUL ( نرم افزاری تهیه شد که با در نظر گرفتن طول و عرض صفحه اصلی و با توجه به اندازه های قطعات و تعداد مورد تقاضا، بهترین الگوی برش ممکن را ارائه می دهد.

کلیدواژه‌ها


1. Agrawal, P.K. (1993). Minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts. European Journal of Operational Research., 64, pp. 410–422.
2. Alatas, B.; Akin, E. A.; Ozers, B.l. )1113(. Chaos-embedded particle swarm optimization algorithms,Chaos, Solitons and Fractals.
3. Arenales, M.; Morabito, R. (1995). An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems. European Journal of Operational Research., 84, pp. 599-617.
5. Beasley, J.E. )1985(. Algorithms for Unconstraind Two-Dimensional Guillotine Cutting. Operation’s Research Society.,Vol.36, No.4, PP.297-306.
6. Beasley, J.E. )1985(. An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure. Operation’s Research., Vol.33, No.1, PP.49-64.
7. Beasley, J.W. )1111(. A Population Heuristic for Constrained Two-Dimensional Non-Guillotine Cutting. http://mscmga.ms.ic.ac.uk/jebihtml.
8. Chambers, M.L.; Dyson, R.G. (1976). The cutting stock problem in the flat glass industry. Operations Research Quarterly., Vol 27, Nr. 4, pp. 949 - 957.
9. Chauny, F.; Loulou, R.; Sadones, S.; Soumis, F. (1987). A two phase heuristic for the two-phase heuristic for strip packing: algorithm and probabilistic analysis. Operational Research Letters, 6, pp. 25–33.
10. Cheng, C.H.; Feiring, B.R.; Cheng, T.C. (1994). The cutting stock problem-a survey. International Journal of Production Economics., 36, pp. 291–305.
11. Christofides, N.; Whitlock, C. (1977). An algorithm for the two dimensional cutting problem. Operations Research., 25, pp. 30–44.
12. Cintra, G.F., et al. (2008). Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research., 191, pp. 61–85.
13. Coffman, E.G.; Garey, M.R.; Johnson, D.S.; Tarjan, R.E. (1980). Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM Journal on Computing., 9, 4, pp. 808-826.
14. Coffman, E.G.; Shor, P.W. (1990). Average-Case Analysis of Cutting and Packing in Two Dimensions. European Journal of Operational Research., 44, 2, pp. 134-145.
15. Cui, Y. (2005). Dynamic programming algorithms for the optimal cutting of equal rectangles. Applied Mathematical Modeling., 29, pp. 1040-1053.
16. Cui, Y. (2006). Simplest optimal cutting patterns for equal rectangles. Operations Research Letters, 34, pp. 630-638.
17. Dietrich, R.D.; Yakowitz, S.J. )1991(. A Rule-Based Aproach to The Trim-Loss Problem. INT.J.PROD.RES., Vol.29, No.20, PP.401-415.
18. Dowsland, K.A.; Dowsland, W.B. (1992). Packing problems. European Journal of Operational Research., 56, pp. 2-14.
19. Dyckhoff, H. )1990(. A typology of cutting and packing problems. European Journal of Operational Research., 44, pp. 145–159.
20. Farley, A.A. (1988). Mathematical programming models for cutting stock problems in the clothing industry. Journal of the Operational Research Society., 39, pp. 41–53.
21. Farley, A.A. (1990). A note on bounding a class of linear programming problems, including cutting stock problems. Operations Research., 38, pp. 922–923.
22. Gass, S. (1985). Linear Programming, Methods and Applications. McGraw-Hill.
23. Gilmore, P.C.; Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research., Vol. 9, pp. 849-859.
24. Gilmore, P.C.; Gomory, R.E. (1965). Multi-stage cutting stock problems of two and more dimensions. Operations Research., 13, pp. 94–120.
25. Gradišar, M.; Jesenko, J.; Resinovič, G. (1997). Optimization of roll cutting in clothing industry. Computer & Operations Research., 24, pp. 945-953.
26. Gradišar, M.; Resinovič, G.; Jesenko, J.; Kljajić, M. (1999). A sequential heuristic procedure for one-dimensional cutting. European Journal of Operational Research., 114, pp. 557-568.
27. Hadjiconstantinou, E.; Christofides, N. (1995). An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research., 83, pp. 39-56.
28. Hadjiconstantinou, E.; Iori, M. (2007). A hybrid genetic algorithm for the two-dimensional single large object placement problem. European Journal of Operational Research., 183, pp. 1150-1166.
29. Haessler, R.W.; Sweeney, P.E. (1991). Cutting stock problems and solution procedures. European Journal of Operational Research., 54, pp. 141-150.
30. Hifi, M.; Ouafi, R. )1977(. Best-first search And Dynamic Programming Methods for Cutting Problems: The cases of One or More Stock Plates. Computers ind.Eng., Vol.32, No.1, PP.187-205,.
31. Jiang, J.Q.; Xing, X.L.; Yang, X.W.; Liang, Y.C. (2004). A Hybrid Algorithm Based on PSO and Genetic Operation and Its Applications For Cutting Stock Problem. Proceedings of The Third Int. Conference on Machine Learning and
Cybernetics., Shangai, pp. 2198-2201.
32. Kantorovich, L.V. )1939(. Mathematical methods of organizing and planning production. Mgmt. Sci.,Vol. , pp.363-422.