Evolutionary Algorithms Approach for Cutting Stock Problem

• Autorzy: Romanowski A. , Nowotniak R. , Kawecki K , Jaworski T. , Chaniecki Z. , Grudzień K.
• Języki publikacji: EN

Abstrakty

EN

This paper contain study of three algorithms for optimisation of use of materials for cutting process. Cutting Stock Problem (CSP) and one dimensional guillotine cat variant of the CSP is introduced. Afterwards three different way of solving the problem are presented. For each of theme one algorithm is proposed. First is creating all the possible solutions and choosing the best one. Second is trying to recreate a human thinking process by using a heuristic search. Third one is inspired by an evolution process in the nature. Design and implementation of each of them is presented. Proposed algorithms are tested and compared to each other and also to the other known solutions.

Słowa kluczowe

EN

CSP; heuristic algorithm; genetic algorithm

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2012
• Tom: Vol. 17, no. 4
• Strony: 297--306
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Romanowski A.

• Institute of Applied Computer Science, Lodz University of Technology, Poland

autor

Nowotniak R.

• Institute of Applied Computer Science, Lodz University of Technology, Poland

autor

Kawecki K

• Institute of Applied Computer Science, Lodz University of Technology, Poland

autor

Jaworski T.

• Institute of Applied Computer Science, Lodz University of Technology, Poland

autor

Chaniecki Z.

• Institute of Applied Computer Science, Lodz University of Technology, Poland

autor

Grudzień K.

• Institute of Applied Computer Science, Lodz University of Technology, Poland

Bibliografia

• [1] C. Nitsche, G. Scheithauer, J. Terno, Tighter relaxations for the cutting stock problem, European Journal of Operational Research, No. 112, pp. 654-663, 1999
• [2] T.H. Cormen , C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Second Edition, The Massachusetts Institute of Technology, 2001
• [3] S.J. Russel, P. Norvig, Artificial Intelligence, A Modern Approach, Second Edition, Pearson Education, 2003
• [4] M. Melanie, An Introduction to Genetic Algorithms, The Massachusetts Institute of Technology, 1996
• [5] B.J. Wagner, A genetic algorithm solution for onedimensional bundled stock cutting, European Journal of Operational Research, No. 117, pp. 368-381, 1999
• [6] G. Schilling, M.C. Georgiadis, An algorithm for the determination of optimal cutting patterns, Computers & Operations Research, No. 29, pp. 1041-1058, 2002
• [7] CSP - cutting stock problem, http://en.wikipedia.org/wiki/Cutting_stock_problem, 2010 (retrieved as of may 2012)
• [8] R. Morabito, L. Belluzzo, Optimising the cutting of wood fibre plates in the hardboard industry, European Journal of Operational Research, No. 183, pp. 1405-1420, 2007
• [9] S. Umetani, M. Yagiura, T. Ibaraki, Onedimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research, No. 146, pp. 388-402, 2003
• [10] E. Hopper, B. Turton, A genetic algorithm for a 2d industrial packing problem, Computers&Industrial Engineering, No. 37, pp. 375-378, 1999
• [11] N. Siu, E. Elghoneimy, Y. Wang, W. Gruver, M. Fleetwood, D. Kotak, Rough mill component scheduling: Heuristic search versus genetic algorithms, IEEE International Conference on Systems, Man and Cybernetics, pp. 4226-4231, 2004
• [12] R. Alvarez-Valdes, A. Parajon, J.M. Tamarit, A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems, Computers & Operations Research, No. 29, pp. 925-947, 2002
• [13] M. Hi, Exact algorithms for unconstrained threedimensional cutting problems: a comparative study, Computers & Operations Research, No. 31, pp. 657-674, 2004
• [14] R. Baldacii, M.A. Boschetti, A cutting-plane approach for the two-dimensional orthogonal nonguillotine cutting problem, European Journal of Operational Research, No. 183, pp. 1136-1149, 2007
• [15] D. Chen, Y. Fu, M. Shang, W. Huang, A quasihuman heuristic algorithm for 2d rectangular strip packing problem, International Symposium on Information Science and Engineering, pp. 392-396, 2008