Top

Journal of Intelligent Manufacturing

Published in:

10-02-2023

Graph neural network comparison for 2D nesting efficiency estimation

Authors: Corentin Lallier, Guillaume Blin, Bruno Pinaud, Laurent Vézard

Published in: Journal of Intelligent Manufacturing | Issue 2/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Minimizing the level of material consumption in textile production is a major concern. The cornerstone of this optimization task is the nesting problem, whose goal is to lay a set of irregular 2D parts out onto a rectangular surface, called the nesting zone, while respecting a set of constraints. Knowing the efficiency—ratio of usable to used up material enables the optimization of several textile production problems. Unfortunately, knowing the efficiency requires the nesting problem to be solved, which is computationally intensive and has been proven to be NP-hard. This paper introduces a regression approach to estimate efficiency without solving the nesting problem. Our approach models the 2D nesting problem as a graph where the nodes are images derived from parts and the edges hold the constraints. The method then consists of combining convolutional neural networks for addressing the image-based aspects and graph neural networks (GNNs) for the constraint aspects. We evaluate several neural message passing approaches on our dataset and obtain results that are sufficiently accurate for enabling several business use cases, where our model best solves this task with a mean absolute error of 1.65. We provide open access to our dataset, whose properties differ from those of other graph datasets found in the literature. This dataset is constructed on 100,000 real customers’ nesting data. Along the way, we compare the performance and generalization capabilities of four GNN architectures obtained from the literature on this dataset.

previous article A knowledge distillation-based multi-scale relation-prototypical network for cross-domain few-shot defect classification

next article Experience from implementing digital twins for maintenance in industrial processes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

https://doi.org/10.5281/zenodo.6610253.

Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research (EJOR), 290(2), 405–421. https://doi.org/10.1016/j.ejor.2020.07.063CrossRef

Bennell, J. A., & Oliveira, J. F. (2009). A tutorial in irregular shape packing problems. Journal of the Operational Research Society, 60(sup1), S93–S105. https://doi.org/10.1057/jors.2008.169CrossRef

Bodnar, C., Frasca, F., & Otter, N., et al (2021) Weisfeiler and Lehman go cellular: CW networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin et al. (Eds.), Advances in neural information processing systems, vol. 34 (pp 2625–2640). Curran Associates, Inc. Retrieved from https://proceedings.neurips.cc/paper/2021/.file/157792e4abb490f99dbd738483e0d2d4-Paper.pdf

Bresson, X., & Laurent, T. (2018) Residual Gated Graph ConvNets. arXiv:1711.07553 [cs, stat] https://doi.org/10.48550/arXiv.1711.07553.

Brockschmidt, M. (2020). GNN-FiLM: Graph neural networks with feature-wise linear modulation. In Proc. of the 37th Int. Conf. on Machine Learning. JMLR.org, ICML’20. https://doi.org/10.5555/3524938.3525045

Chaudhari, S., Mithal, V., Polatkan, G., et al. (2021). An attentive survey of attention models. ACM Transactions on Intelligent Systems and Technology. https://doi.org/10.1145/3465055CrossRef

Dosovitskiy, A., Beyer, L., Kolesnikov, A., et al. (2021) An image is worth 16x16 words: Transformers for image recognition at scale. In Int. Conf. on Learning Representations. https://openreview.net/forum?id=YicbFdNTTy.

Dowsland, K. A., Vaid, S., & Dowsland, W. B. (2002). An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research (EJOR), 141(2), 371–381. https://doi.org/10.1016/S0377-2217(02)00131-5CrossRef

Dwivedi, V. P., & Bresson, X. (2021). A generalization of transformer networks to graphs. In Deep learning on graphs: Method and applications (DLG-AAAI). https://doi.org/10.48550/arXiv.2012.09699.

Dwivedi, V. P., Joshi, C. K., Laurent, T., et al (2020) Benchmarking graph neural networks. arXiv:2003.00982 [cs, stat] https://doi.org/10.48550/arXiv.2003.00982.

ESICUP. (2021). Cutting and packing—datasets. Retrieved from https://www.euro-online.org/websites/esicup/data-sets/#1535972088237-bbcb74e3-b507.

Gilmer, J., Schoenholz, S. S., Riley, P. F., et al. (2017). Neural message passing for quantum chemistry. Proceedings of Machine Learning Research (PMLR). https://doi.org/10.5555/3305381.3305512CrossRef

Gomes, A. M., & Oliveira, J. F. (1999). Nesting irregular shapes with simulated annealing. In Extended Abstracts of MIC1999–III Metaheuristics Int Conf (pp. 19–22).

Gong, L., & Cheng, Q. (2019). Exploiting edge features in graph neural networks. In Computer Vision and Pattern Recognition Conf (CVPR). https://doi.org/10.1109/CVPR.2019.00943.

Goodman, E., Tetelbaum, A., & Kureichik, V. (1994). A genetic algorithm approach to compaction, bin packing, and nesting problems. Tech. rep., Michian State University. http://garage.cse.msu.edu/papers/GARAGe94-4.pdf.

Henninger, C. E., Alevizou, P. J., & Oates, C. J. (2016). What is sustainable fashion? Journal of Fashion Marketing and Management, 20(4), 400–416. https://doi.org/10.1108/JFMM-07-2015-0052CrossRef

Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In Int. Conf. on Learning Representations. Retrieved from https://openreview.net/forum?id=SJU4ayYgl.

Laga, H., Takahashi, H., & Nakajima, M. (2006). Spherical wavelet descriptors for content-based 3D model retrieval. In Int Conf on shape modeling and applications (SMI). https://doi.org/10.1109/SMI.2006.39.

Lecun, Y., Bottou, L., Bengio, Y., et al. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278–2324. https://doi.org/10.1109/5.726791CrossRef

Lee, J, Lee, I., & Kang, J. (2019). Self-attention graph pooling. In Proc. of the 36th Int. Conf. on Machine Learning (ICML), PMLR. Retrieved from http://proceedings.mlr.press/v97/lee19c/lee19c.pdf.

Li, Z., & Milenkovic, V. (1995). Compaction and separation algorithms for non-convex polygons and their applications. European Journal of Operational Research (EJOR), 84(3), 539–561. https://doi.org/10.1016/0377-2217(95)00021-HCrossRef

Li, Y., Tarlow, D., Brockschmidt, M., et al (2017) Gated graph sequence neural networks. In Int. Conf. on Learning Representations (ICLR). https://doi.org/10.48550/arXiv.1511.05493.

Liu, H., & He, Y. (2006). Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle. Journal of Zhejiang University-Science A, 7(4), 570–576. https://doi.org/10.1631/jzus.2006.A0570CrossRef

Luong, T., Pham, H., & Manning, C. D. (2015). Effective approaches to attention-based neural machine translation. In Proc. of Conf. on Empirical Methods in Natural Language Processing (pp 1412–1421). Association for Computational Linguistics, Lisbon, Portugal. https://doi.org/10.18653/v1/D15-1166.

Mirhoseini, A., Goldie, A., Yazgan, M., et al. (2021). A graph placement methodology for fast chip design. Nature, 594(7862), 207–212. https://doi.org/10.1038/s41586-021-03544-wCrossRef

Mo, Y., Wu, Q., Li, X., et al. (2021). Remaining useful life estimation via transformer encoder enhanced by a gated convolutional unit. Journal of Intelligent Manufacturing, 32(7), 1997–2006. https://doi.org/10.1007/s10845-021-01750-xCrossRef

Oliveira, J. F. C., & Ferreira, J. A. S. (1993). Algorithms for nesting problems. In G. Fandel, W. Trockel, & R. V. V. Vidal (Eds.), Applied simulated annealing (Vol. 396, pp. 255–273). Springer. https://doi.org/10.1007/978-3-642-46787-5_13CrossRef

Oztemel, E., & Gursev, S. (2020). Literature review of industry 4.0 and related technologies. Journal of Intelligent Manufacturing, 31(1), 127–182. https://doi.org/10.1007/s10845-018-1433-8CrossRef

Paszke, A., Gross, S., Massa, F., et al (2019) Pytorch: An imperative style, high-performance deep learning library. In Proc. of the 33rd Int. Conf. on Neural Information Processing Systems (p. 721). Curran Associates Inc. https://doi.org/10.5555/3454287.3455008.

Popescu, A., Polat-Erdeniz, S., Felfernig, A., et al. (2021). An overview of machine learning techniques in constraint solving. Journal of Intelligent Information Systems. https://doi.org/10.1007/s10844-021-00666-5CrossRef

Rissanen, T. I. (2013). Zero-waste fashion design: A study at the intersection of cloth, fashion design and pattern cutting. Thesis, University of Technology Sydney. Retrieved from http://hdl.handle.net/10453/23384.

Saramaki, J., Kivela, M., Onnela, J. P., et al. (2007). Generalizations of the clustering coefficient to weighted complex networks. Physical Review E, 75(2), 027105. https://doi.org/10.1103/PhysRevE.75.027105CrossRef

Scarselli, F., Gori, M., Tsoi, A. C., et al. (2009). The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 61–80. https://doi.org/10.1109/TNN.2008.2005605CrossRef

Schlichtkrull, M., Kipf, T. N., Bloem, P., et al. (2018). Modeling relational data with graph convolutional networks. In European semantic web conf. (pp 593–607). Springer. https://doi.org/10.1007/978-3-319-93417-4_38.

Schütt, K. T., Kindermans, P. J., Sauceda, H. E., et al. (2017). SchNet: A continuous-filter convolutional neural network for modeling quantum interactions. In Proc. of the 31st Int. Conf. on Neural Information Processing Systems (pp. 992–1002). Curran Associates Inc. NIPS’17. https://doi.org/10.5555/3294771.3294866.

Soong, Z. W. (2015). Reinforcement learning for the 2D—packing problem. PhD thesis. The Hong Kong University of Science and Technology. https://doi.org/10.14711/thesis-b1514577.

Vaswani, A., Shazeer, N., Parmar, N., et al. (2017). Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio et al (Eds.), Advances in neural information processing systems, vol. 30. Curran Associates, Inc. Retrieved from https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.

Veličković, P., Cucurull, G., & Casanova, A., et al (2018) Graph attention networks. In Int Conf on Learning Representations (ICLR) (p. 12). https://doi.org/10.17863/CAM.48429.

Wang, B., Tao, F., Fang, X., et al. (2021). Smart manufacturing and intelligent manufacturing: A comparative review. Engineering, 7(6), 738–757. https://doi.org/10.1016/j.eng.2020.07.017CrossRef

Wang, M., Zheng, D., & Ye, Z., et al (2020) Deep graph library: Towards efficient and scalable deep learning on graphs. In Computing research repository (CoRR). Retrieved from https://www.dgl.ai/.

Xie, T., & Grossman, J. C. (2018). Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Physical Review Letters, 120(14), 145301. https://doi.org/10.1103/PhysRevLett.120.145301CrossRef

Xu, D., & Li, H. (2008). Geometric moment invariants. Pattern Recognition, 41(1), 240–249. https://doi.org/10.1016/j.patcog.2007.05.001CrossRef

Xu, K., Hu, W., & Leskovec, J., et al. (2019). How powerful are graph neural networks? In Int. Conf. on Learning Representations. Retrieved from https://openreview.net/forum?id=ryGs6iA5Km.

Xu, Y., Thomassey, S., & Zeng, X. (2020). An application of machine learning to marker prediction in garment industry: Marker length estimation by neural network for the exponentially increasing magnitude of possible size combinations. In Proc. of the 3rd Int. Conf. on Applications of Intelligent Systems (pp. 1–5). ACM. https://doi.org/10.1145/3378184.3378219.

Ying, C., Cai, T., & Luo, S. et al (2021). Do transformers really perform badly for graph representation? In A. Beygelzimer, Y. Dauphin, P. Liang, et al (Eds.), Advances in neural information processing systems. Retrieved from https://openreview.net/forum?id=OeWooOxFwDa.

Yun, S., Jeong, M., & Kim, R., et al (2019) Graph transformer networks. In H. Wallach, H. Larochelle, A. Beygelzimer et al (Eds.), Advances in neural information processing systems, vol 32. Curran Associates, Inc. Retrieved fromhttps://proceedings.neurips.cc/paper/2019/file/9d63484abb477c97640154d40595a3bb-Paper.pdf.

Title: Graph neural network comparison for 2D nesting efficiency estimation
Authors: Corentin Lallier
Guillaume Blin
Bruno Pinaud
Laurent Vézard
Publication date: 10-02-2023
Publisher: Springer US
Published in: Journal of Intelligent Manufacturing / Issue 2/2024
Print ISSN: 0956-5515
Electronic ISSN: 1572-8145
DOI: https://doi.org/10.1007/s10845-023-02084-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 2/2024

Rule-based visualization of faulty process conditions in the die-casting manufacturing

Intelligent control system for 3D inkjet printing

A domain adaptation method for bearing fault diagnosis using multiple incomplete source data

Machine learning enabled optimization of showerhead design for semiconductor deposition process

Global and local representation collaborative learning for few-shot learning

Heterogeneous demand–capacity synchronization for smart assembly cell line based on artificial intelligence-enabled IIoT

Premium Partners