Genetic Algorithm for Panel Cutting Stock on CUDA Platform

Abstract:

The problem of placing a number of specific shapes on a raw material in order to maximize material utilization is commonly encountered in the production of steel bars and plates, papers, glasses, etc. In this paper, we presented a genetic algorithm for steel grating nesting design. For application in large-scale discrete optimization problems, we also implemented this algorithm with CUDA based on parallel computation. Experimental results show that under genetic algorithm invoking with CUDA scheme, we can obtain satisfied solutions to steel grating nesting problem with high performance.

• Periodical: Advanced Materials Research (Volumes 712-715)
• Pages: 2569-2575
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.712-715.2569
• Online since: June 2013
• Authors: Wen Wu Xie*, Tao Ning
• Keywords: CUDA, Genetic Algorithm (GA), Nesting, Steel Grating

References

[1] Fowler, R. J., Paterson, M. S., & Tatimoto, S. L. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12, 133–137, 1981.

DOI: 10.1016/0020-0190(81)90111-3

[2] Holland, J. H. Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press, 1975.

[3] Hopper, E., & Turton, B. C. H. A genetic algorithm for a 2D industrial packing problem. Computers & Industrial Engineering, 37(1–2), 375–378, 1999.

DOI: 10.1016/s0360-8352(99)00097-2

[4] Hopper, E., & Turton, B. C. H. A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artificial Intelligence Review, 16, 257–300, 2001.

[5] K.A. Dowsland.,& W.B. Dowsland, Solution approaches to irregular nesting problems, European Journal of Operations Research Elsevier, vol. 84, p.506–521, 1995.

DOI: 10.1016/0377-2217(95)00019-m

[6] Dowsland, K. A., & Dowsland, W. B. Solution approaches to irregular nesting problems. European Journal of Operational Research, 84(3), 506–521, 1995.

DOI: 10.1016/0377-2217(95)00019-m

[7] Fischer, A. D., & Dagli, C. H. Employing subgroup evolution for irregular-shape nesting. Journal of Intelligent Manufacturing, 15, 187–199, 2004.

DOI: 10.1023/b:jims.0000018032.38317.f3

[8] Crispin, A., Clay, P., & Taylor, G. Genetic algorithm coding methods for leather nesting. Applied Intelligence, 23(1), 9–20, 2005.

DOI: 10.1007/s10489-005-2368-2

[9] Gen, M., & Cheng, R. Genetic algorithms and engineering design. New York: Wiley-Interscience, 1997.

[10] http://www.nvidia.com/object/cuda_home_new.html

[11] S.M.A. Suliman, A sequential heuristic procedure for the two-dimensional cutting stock problem, International Journal of Production Economics, vol. 99, 177-185, 2006.

DOI: 10.1016/j.ijpe.2004.12.017

[12] Speras, W. M., & DeJong, K. A. On the virtues of parameterized uniform crossover. Proceedings of Fourth International Conference Genetic Algorithms, 230–236, 1991.

[13] Tobias B, Lothar T. A comparison of selection schemes used in evolutionary algorithms. Evol Comput 1996;4:361–94.

[14] Rajvi, S., P.J. Narayanan., & Kishore, K. GPU-Accelerated Genetic Algorithms, cvit.iiit.ac.in.

[15] Denis,Robilliard., Virginie,Marion., &Cyril Fonlupy. High Performance Genetic Programming on GPU. CA. 13, 85-93, (2009)

[16] Mohamed, W., & Asim, M. Optimization of Parallel Genetic Algorithm for nVidia GPUs, 2011.