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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Combining Bird Flight Algorithm and CUL Heuristic Algorithm for On-Demand Two-Dimensional Non-Guilline Cutting Problem

نویسندگان [English]

  • Faezeh Asadian Ardakani 1
  • Ali Morovati Sharifabadi 2
1 M.A. Student.
2 Assistant Professor, Yazd University.
چکیده [English]

In this paper, the problem of two-dimensional shear is investigated with demand. In this case, by cutting large rectangular sheets, the smaller rectangles needed should be produced in a way that minimizes waste or the number of sheets consumed while supplying them. The shear problem is one of the NP-Hard problems that precise methods cannot solve in practice. Therefore, in this paper, using a bird flight algorithm, a meta-heuristic algorithm for solving the two-dimensional shear problem is presented. In order to improve the efficiency of this algorithm and to avoid overlap in the shear problem, the CUL heuristic algorithm was employed. Also, to evaluate the results of the proposed algorithm, a combination of PSO and CUL algorithms (software) was developed that provides the best possible cutting pattern considering the length and width of the home screen and considering the size of the components and the number requested.

کلیدواژه‌ها [English]

  • Bird Flight Algorithm
  • Discrete Bird Flight Algorithm
  • CUL Algorithm
  • 2D Cutting Problem
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.