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

Document Type : Original Article

Authors

1 M.A. Student.

2 Assistant Professor, Yazd University.

Abstract

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.

Keywords

References

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.

Files

Share

How to cite

Statistics