Hyper-Heuristic Approach for Improving Marker Efficiency

• Autorzy: Domović D. , Rolich T. , Golub M.

Identyfikatory

DOI

10.1515/aut-2018-0026

• Języki publikacji: EN

Abstrakty

EN

Marker planning is an optimization arrangement problem, where a set of cutting parts need to be placed on a thin paper without overlapping to create a marker – an exact diagram of cutting parts that will be cut from a single spread. An optimal marker that utilizes the length of textile material has to be obtained. The aim of this research was to develop novel algorithms for obtaining an efficient marker that would achieve competitive results and optimize the garment production in terms of improving the utilization of textile material. In this research, a novel Grid heuristic was introduced for obtaining a marker, alongside its improvement methods: Grid-BLP and Grid-Shaking. These heuristics were hybridized with genetic algorithm that determined the placement order of cutting parts using the newly introduced All Equal First (AEF) placement order. A novel individual representation for genetic algorithm was designed that was composed of order sequence, rotation detection and the choice of placement algorithm (hyper-heuristic). Experiments were conducted to determine the best marker making method, and hyper-heuristic efficiency. The implementation and experiments were conducted in MATLAB using GEATbx toolbox on five datasets from the garment industry: ALBANO, DAGLI, MAO, MARQUES and MAN SHIRT. Marker efficiency in percentage was recorded with best results: 84.50%, 80.13%, 79.54%, 84.67% and 86.02% obtained for the datasets respectively. The most efficient heuristic was Grid-Shaking. Hyper-heuristic applied Grid-Shaking in 88% of times. The created algorithm is independent of cutting parts’ shape. It can produce markers of arbitrary shape and is flexible in terms of expansion to new instances from the garment industry (leather nesting, avoiding damaged areas of material, marker making with materials with patterns).

Słowa kluczowe

EN

marker making; lay planning; production optimization; CAD/CAE; genetic algorithm; hyper-heuristics

PL

przygotowanie wzoru; optymalizacja produkcji; CAD/CAE; algorytm genetyczny; hiperheurystyki

• Wydawca: Lodz University of Technology, Faculty of Material Technologies and Textile Design
• Czasopismo: Autex Research Journal
• Rocznik: 2018
• Tom: Vol. 18, no. 4
• Strony: 348--363
• Opis fizyczny: Bibliogr. 45 poz.

Twórcy

autor

Domović D.

• University of Zagreb, Faculty of Textile Technology, Department of Fundamental, Natural and Technical Sciences, Prilaz baruna Filipovića 28a, 10000 Zagreb, Croatia, tel.:[phone], fax: + 385 1 3712 599

autor

Rolich T.

• University of Zagreb, Faculty of Textile Technology, Department of Fundamental, Natural and Technical Sciences, Prilaz baruna Filipovića 28a, 10000 Zagreb, Croatia, tel.:[phone], fax: + 385 1 3712 599

autor

Golub M.

• University of Zagreb, Faculty of Electrical Engineering and Computing, Department of electronics, microelectronics, computer and intelligent systems, Unska 3, 10000 Zagreb, Croatia, tel.:[phone], fax: + 385 1 6129 653

Bibliografia

• [1] Dumishllari, E., & Guxho, G. (2016). Influence of Lay Plan Solution in Fabric Efficiency and Consume in Cutting Section. Autex Research Journal, 16(4). doi:10.1515/aut-2015-0055
• [2] Yesilpinar, S., & Aytac, V. (2009). An Approach Aimed at Fabric Consumption in Shirt Production. Textile Research Journal, 79(5), 461–467. doi:10.1177/0040517508090491
• [3] Ujević, D., Rogale, D., & Hrastinski, M. (2010). Tehnike konstruiranja i modeliranja odjeće, treće dopunjeno i prošireno izdanje. Zagreb: Zrinski d. d.
• [4] Guo, Z., Wong, W., Leung, S., & Li, M. (2011). Applications of artificial intelligence in the apparel industry: a review. Textile Research Journal, 81(18), 1871–1892. doi:10.1177/0040517511411968
• [5] Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109–1130. doi:10.1016/j.ejor.2005.12.047
• [6] Egeblad, J. (2008). Heuristics for Multidimensional Packing Problems. Københavns Universitet, Faculty of Science, Datalogisk Institut, Department of Computer Science. Retrieved from http://forskningsbasen.deff.dk/Share.external?sp=S659a8b80-ac03-11de-bc73-000ea68e967b&sp=Sku
• [7] Ramesh Babu, A., & Ramesh Babu, N. (2001). A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Computer-Aided Design, 33(12), 879–891.
• [8] Segenreich, S. A., & Braga, L. M. P. F. (1986). Optimal nesting of general plane figures: A Monte Carlo heuristical approach. Computers & Graphics, 10(3), 229–237. doi:http://dx.doi.org/10.1016/0097-8493(86)90007-5
• [9] Bennell, J. A., & Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), 397–415. doi:10.1016/j.ejor.2006.11.038
• [10] Mahadevan, Anantharam. (n.d.). Optimization in Computer-aided Pattern Packing (Marking, Envelopes) (1984). North Carolina State University.
• [11] Sato, A. K., Martins, T. C., & Tsuzuki, M. S. G. (2012). An algorithm for the strip packing problem using collision free region and exact fitting placement. Computer-Aided Design, 44(8), 766–777. doi:10.1016/j.cad.2012.03.004
• [12] Ghosh, P. K. (1991). An algebra of polygons through the notion of negative shapes. CVGIP: Image Understanding, 54(1), 119–144.
• [13] Fujita, K., Akagi, S., & Hirokawa, N. (1993). Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm. In Proceedings of the 19th annual ASME design automation conference (Vol. 1, pp. 477–484). Retrieved from http://www.waka.kindai.ac.jp/tea/hirokawa/hirokawa/research/papers/1993/09_ASME_DAC_nesting.pdf
• [14] Hopper, E., & Turton, B. (1999). A genetic algorithm for a 2D industrial packing problem. Computers & Industrial Engineering, 37(1), 375–378.
• [15] Burke, E., Hellier, R., Kendall, G., & Whitwell, G. (2006). A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem. Operations Research, 54(3), 587–601. doi:10.1287/opre.1060.0293
• [16] Dowsland, K. A., Vaid, S., & Dowsland, W. B. (2002). An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research, 141(2), 371–381.
• [17] 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. Retrieved from http://clb.demon.fi/files/RectangleBinPack.pdf
• [18] Shalaby, M. A. (2013). A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem. American Journal of Operations Research, 03(02), 268–278. doi:10.4236/ajor.2013.32024
• [19] Burke, E., & Kendall, G. (1999). Applying ant algorithms and the no fit polygon to the nesting problem. In Advanced Topics in Artificial Intelligence (pp. 453–464). Springer. Retrieved from http://link.springer.com/chapter/10.1007/3-540-46695-9_38
• [20] Fischetti, M., & Luzzi, I. (2009). Mixed-integer programming models for nesting problems. Journal of Heuristics, 15(3), 201–226.
• [21] Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013). Hyper-heuristics: a survey of the state of the art. Journal of the Operational Research Society, 64(12), 1695–1724. doi:10.1057/jors.2013.71
• [22] Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Woodward, J. R. (2010). A Classification of Hyper-heuristic Approaches. In M. Gendreau & J.-Y. Potvin (Eds.), Handbook of Metaheuristics (Vol. 146, pp. 449–468). Boston, MA: Springer US. doi:10.1007/978-1-4419-1665-5_15
• [23] Garrido, P., & Riff, M. C. (2007). Collaboration Between Hyperheuristics to Solve Strip-Packing Problems. In P. Melin, O. Castillo, L. T. Aguilar, J. Kacprzyk, & W. Pedrycz (Eds.), Foundations of Fuzzy Logic and Soft Computing (pp. 698–707). Springer Berlin Heidelberg.
• [24] Bhanu, S. M. S., & Gopalan, N. P. (2008). A Hyper-Heuristic Approach for Efficient Resource Scheduling in Grid. International Journal of Computers Communications & Control, 3(3), 249. doi:10.15837/ijccc.2008.3.2393
• [25] Terashima-Marín, H., Farías Zárate, C. J., Ross, P., & Valenzuela-Rendón, M. (2006). A GA-based method to produce generalized hyper-heuristics for the 2D-regular cutting stock problem (p. 591). ACM Press. doi:10.1145/1143997.1144102
• [26] EURO Special Interest Group on Cutting and Packing. (2015). EURO Special Interest Group on Cutting and Packing. Retrieved January 29, 2015, from https://paginas.fe.up.pt/~esicup/
• [27] Domovic, D., & Rolich, T. (2015). Solving strip-packing problem using sequence pair. doi:10.1109/MIPRO.2015.7160455
• [28] Domović, D., Rolich, T., Grundler, D., & Bogović, S. (n.d.). Algorithms for 2D Nesting Problem Based on the No-Fit Polygon. In Proceedings of the 37th International Convention MIPRO 2014: CIS - Intelligent Systems (pp. 1344–1349). Presented at the 2014 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), Opatija, Croatia: Croatian Society for Information and Communication Technology, Electronics and Microelectronics - MIPRO.
• [29] Toledo, F. M. B., Carravilla, M. A., Ribeiro, C., Oliveira, J. F., & Gomes, A. M. (2013). The Dotted-Board Model: A new MIP model for nesting irregular shapes. International Journal of Production Economics, 145(2), 478–487. doi:10.1016/j.ijpe.2013.04.009
• [30] Chazelle, B. (1983). The Bottom-Left Bin-Packing Heuristics: An Efficient Implementation. IEEE Transactions on Computers, c–32(8), 697–707.
• [31] Jakobs, S. (1996). On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88(1), 165–181.
• [32] Hopper, E. (2000). Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods (Doctoral Thesis). University of Wales. Cardiff. Retrieved from http://vmk.ugatu.ac.ru/c%26p/article/HOPPER/PhDisser/part1.pdf
• [33] Golub, M. (2004). Genetski algoritam - prvi dio. Retrieved February 24, 2014, from http://www.zemris.fer.hr/~golub/ga/ga_skripta1.pdf
• [34] Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2006). Algorithms. Retrieved from http://www.cse.ucsd.edu/~dasgupta/mcgrawhill/
• [35] Pohlheim, H. (2007, March). GEATbx - Genetic and Evolutionary Algorithms Toolbox in Matlab. GEATbx - The Genetic and Evolutionary Algorithm Toolbox for Matlab. Retrieved February 21, 2014, from http://www.geatbx.com/
• [36] Pohlheim, H. (1998). Genetic and Evolutionary Algorithm Toolbox for use with MATLAB. Dept. Comput. Sci., Univ. Ilmenau, Ilmenau, Germany. Retrieved from http://www.geatbx.com/download/GEATbx_Tutorial_v33c.pdf
• [37] Factorial of input - MATLAB factorial. (n.d.). Retrieved December 6, 2016, from https://www.mathworks.com/help/matlab/ref/factorial.html?requestedDomain=www.mathworks.com
• [38] Knuth, D. E. (1997). The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.
• [39] Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc.
• [40] Pohlheim, H. (2003). Evolutionary Algorithms. Springer, Heidelberg. Retrieved from http://www.geatbx.com/download/GEATbx_Intro_Algorithmen_v37.pdf
• [41] Schlierkamp-Voosen, D., & Mühlenbein, H. (1993). Predictive models for the breeder genetic algorithm. Evolutionary Computation, 1(1), 25–49.
• [42] Egeblad, J., Nielsen, B. K., & Odgaard, A. (2007). Fast neighborhood search for two- and three-dimensional nesting problems. European Journal of Operational Research, 183(3), 1249–1266. doi:http://dx.doi.org/10.1016/j.ejor.2005.11.063
• [43] Bennell, J. A., & Song, X. (2010). A beam search implementation for the irregular shape packing problem. Journal of Heuristics, 16(2), 167–188. doi:10.1007/s10732-008-9095-x
• [44] Optitex. (2017). Retrieved February 27, 2017, from http://optitex.com/
• [45] NestLib. (2018). Retrieved June 2, 2018, from https://nestlib.geometricglobal.com/

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).