Abstract
Cutting stock problem is an important problem that arises in a variety of industrial applications. This research constructs an irregular-shaped nesting approach for two-dimensional cutting stock problem. The techniques of shape similarity are utilized, drawn from computer vision and artificial intelligence. These techniques enable the approach to find potential matches of the unplaced pieces within the void regions of the sheet, and thus the packing density and the performance of solutions are highly improved. The proposed approach is able to deal with complex shapes in industrial application and achieve high-quality solution with shorter computational time. We evaluate the proposed method using 15 established benchmark problems available from the EURO Special Interest Group on Cutting and Packing. The results demonstrate the effectiveness and high efficiency of the proposed approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3), 1109–1130 (2007)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Jakobs, S.: On genetic algorithms for the packing of polygons. European Journal of Operational Research 88(1), 165–181 (1996)
Gomes, A.M., Oliveira, J.F.: A 2-exchange heuristic for nesting problems. European Journal of Operational Research 141(2), 359–370 (2002)
Burke, E.K., Hellier, R.S.R., Kendall, G., Whitwell, G.: Irregular Packing Using the Line and Arc No-Fit Polygon. Oper. Res. 58(4), 1–23 (2010)
Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T.: Tools of mathematical modelling of arbitrary object packing problems. Annals of Operations Research 179, 343–368 (2010)
Chernov, N., Stoyan, Y.G., Romanova, T.: Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications 43(5), 535–553 (2010)
Gomes, A.M., Oliveira, J.F.: Solving irregular strip packing problems by hybridizing simulated annealing and linear programming. European Journal of Operational Research 171(3), 811–829 (2006)
Oliveira, J.F., Gomes, A.M., Ferreira, J.S.: TOPOS – a new constructive algorithm for nesting problems. OR Spektrum 22(2), 263–284 (2000)
Burke, E.K., Hellier, R.S.R., Kendall, G., Whitwell, G.: A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Oper. Res. 54(3), 587–601 (2006)
Bouganis, A., Shanahan, M.: A vision-based intelligent system for packing 2-D irregular shapes. IEEE Transactions on Automation Science and Engineering 4(3), 382–394 (2007)
Bennell, J.A., Oliveira, J.F.: The geometry of nesting problems: A tutorial. Eur. J. Oper. Res. 184, 397–415 (2008)
Wong, W.K., Zeng, X.H., Au, W.M.R.: A decision support tool for apparel coordination through integrating the knowledge-based attribute evaluation expert system and the T-S fuzzy neural network. Expert Systems with Applications 36(2), 2377–2390 (2009)
Yuen, C.W.M., Wong, W.K., Qian, S.Q., Chan, L.K., Fung, E.H.K.: A hybrid model using genetic algorithm and neural network for classifying garment defects. Expert Systems with Applications 36(2), 2037–2047 (2009a)
Guo, Z.X., Wong, W.K., Leung, S.Y.S.: A genetic-algorithm-based optimization model for scheduling flexible assembly lines. International Journal of Advanced Manufacturing Technology 36(1-2), 156–168 (2008a)
Yuen, C.W.M., Wong, W.K., Qian, S.Q., Chan, L.K., Fung, E.H.K.: Fabric stitching inspection using segmented window technique and BP neural network. Textile Research Journal 79(1), 24–35 (2009b)
Poshyanonda, P., Dagli, C.H.: Genetic neuro-nester. Journal of Intelligent Manufacturing 15(2), 201–218 (2004)
Wong, W.K., Wang, X.X., Mok, P.Y., Leung, S.Y.S., Kwong, C.K.: Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach. Expert Systems with Applications 36, 3489–3496 (2009)
Dagli, C.H., Hajakbari, A.: Simulated annealing approach for solving stock cutting problem. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernatics, pp. 221–223 (1990)
Sajjanhar, A., Lu, G.: A grid based shape indexing and retrieval method. Austral. Comput. J. 29, 131–140 (1997)
Zhang, D., Lu, G.: Content-based shape retrieval using different shape descriptors: a comparative study. In: Proc. IEEE Int. Conf. Multimedia and Expo, pp. 317–320 (2001)
Del Valle, A.M., De Queiroz, T.A., Miyazawa, F.K., Xavier, E.C.: Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape. Expert Systems with Applications 39(16), 12589–12598 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xu, Y., Yang, G., Pan, C. (2013). A Heuristic Approach Based on Shape Similarity for 2D Irregular Cutting Stock Problem. In: Li, K., Li, S., Li, D., Niu, Q. (eds) Intelligent Computing for Sustainable Energy and Environment. ICSEE 2012. Communications in Computer and Information Science, vol 355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37105-9_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-37105-9_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37104-2
Online ISBN: 978-3-642-37105-9
eBook Packages: Computer ScienceComputer Science (R0)