OPTIMIZATION OF TWO DIMENSIONAL CUTTING STOCK PROBLEM USING EVOLUTIONARY ALGORITHMS
DOI:
https://doi.org/10.24867/32BE18PopovicKeywords:
2D Cutting stock problem, Genetic algorithm, Evolutionary programming, Tabu searchAbstract
This paper presents two evolutionary algorithms for the solution of 2D cutting stock problem: genetic algorithm and evolutionary programming. Two data structures were implemented for the representation of inidividuals, along with various mechanisms for selection, crossover and mutation. A variation of genetic algorithm that applies tabu search instead of standard mutation mechanisms was also implemented. The algorithms were evaluated on benchmark problems that require cutting up to 2700 elements.
References
[1] Mellouli, A. and Dammak, A., 2008. An algorithm for the two-dimensional cutting-stock problem based on a pattern generation procedure. Inf Manag Sci, 19(2), pp.201-218.
[2] Gharsellaoui, H. and Hasni, H., 2011. An hybrid genetic algorithm for two-dimensional cutting problems using guillotine cuts. In Proceedings of the International Conference on Genetic and Evolutionary Methods (GEM) (p. 1). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp).
[3] Ono, T. and Ikeda, T., 1999, July. Optimizing twodimensional guillotine cut by genetic algorithms. In Proc. of the Ninth AJOU-FIT-NUST Joint Seminar (pp. 40-47).
[4] Jylänki, J., 2010. A thousand ways to pack the bin-a practical approach to two-dimensional rectangle bin packing. retrived from http://clb. demon. fi/files/RectangleBinPack. Pdf
[5] Glover, F., 1990. Tabu search: A tutorial. Interfaces, 20(4), pp.74-94.
[6] Jebari, K. and Madiafi, M., 2013. Selection methods for genetic algorithms. International Journal of Emerging Sciences, 3(4), pp.333-344
[7] https://github.com/Oscar-Oliveira/ORDatasets/tree/master/Cutting-andPacking/2D/Datasets/C
[8] https://github.com/Oscar-Oliveira/ORDatasets/tree/master/Cutting-andPacking/2D/Datasets/AB
