IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v28y2017i8d10.1007_s10845-015-1067-z.html
   My bibliography  Save this article

An optimizing model to solve the nesting problem of rectangle pieces based on genetic algorithm

Author

Listed:
  • Hongtao Tang

    (Wuhan University of Technology)

  • Xixing Li

    (Wuhan University of Technology)

  • Shunsheng Guo

    (Wuhan University of Technology)

  • Shuwei Liu

    (Wuhan University of Technology)

  • Li Li

    (Wuhan University of Technology)

  • Lang Huang

    (Wuhan University of Technology)

Abstract

In the process of cement equipment manufacturing, the demand of rectangle pieces of steel structure is very large. The traditional manual nesting, which is simply cutting by hand-making according to the arrangement of the number and size, causes the low efficiency and material wasting. To solve the problem above, this paper proposes an optimizing model for nesting problem of rectangle pieces. Firstly, with the aim of the maximum utilization ratio of the sheet, the optimization mathematical model for nesting problem of rectangle pieces is established. The lowest horizontal line searching algorithm is described in detail. Secondly, the mathematical model is solved to get the optimal solution by the combination of genetic algorithm and the lowest horizontal line searching algorithm. In the solution process, this paper presents the methods of gene encoding and decoding, definition of fitness function, the design of genetic operators and the design of algorithm operating parameters. Finally, we use one sheet as an example to illustrate the proposed model and algorithm process. Experimental results have shown that the proposed approach is able to achieve rectangle pieces nesting with the maximum material utilization ratio.

Suggested Citation

  • Hongtao Tang & Xixing Li & Shunsheng Guo & Shuwei Liu & Li Li & Lang Huang, 2017. "An optimizing model to solve the nesting problem of rectangle pieces based on genetic algorithm," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1817-1826, December.
    • Handle: RePEc:spr:joinma:v:28:y:2017:i:8:d:10.1007_s10845-015-1067-z
    DOI: 10.1007/s10845-015-1067-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-015-1067-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10845-015-1067-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. H. Terashima-Marín & P. Ross & C. Farías-Zárate & E. López-Camacho & M. Valenzuela-Rendón, 2010. "Generalized hyper-heuristics for solving 2D Regular and Irregular Packing Problems," Annals of Operations Research, Springer, vol. 179(1), pages 369-392, September.
    2. Wolf, Christian & Koberstein, Achim, 2013. "Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method," European Journal of Operational Research, Elsevier, vol. 230(1), pages 143-156.
    3. B Kiraz & A Ş Etaner-Uyar & E Özcan, 2013. "Selection hyper-heuristics in dynamic environments," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1753-1769, December.
    4. Gomes, A. Miguel & Oliveira, Jose F., 2002. "A 2-exchange heuristic for nesting problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 359-370, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Igor Kierkosz & Maciej Łuczak, 2019. "A one-pass heuristic for nesting problems," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 29(1), pages 37-60.
    2. Eunice López-Camacho & Gabriela Ochoa & Hugo Terashima-Marín & Edmund Burke, 2013. "An effective heuristic for the two-dimensional irregular bin packing problem," Annals of Operations Research, Springer, vol. 206(1), pages 241-264, July.
    3. Miguel Santoro & Felipe Lemos, 2015. "Irregular packing: MILP model based on a polygonal enclosure," Annals of Operations Research, Springer, vol. 235(1), pages 693-707, December.
    4. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    5. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    6. Rodríguez, Jesús A. & Anjos, Miguel F. & Côté, Pascal & Desaulniers, Guy, 2021. "Accelerating Benders decomposition for short-term hydropower maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 289(1), pages 240-253.
    7. J A Bennell & J F Oliveira, 2009. "A tutorial in irregular shape packing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 93-105, May.
    8. Martin Biel & Mikael Johansson, 2022. "Efficient Stochastic Programming in Julia," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1885-1902, July.
    9. Burke, E.K. & Hellier, R.S.R. & Kendall, G. & Whitwell, G., 2007. "Complete and robust no-fit polygon generation for the irregular stock cutting problem," European Journal of Operational Research, Elsevier, vol. 179(1), pages 27-49, May.
    10. Yu, M.T. & Lin, T.Y. & Hung, C., 2009. "Active-set sequential quadratic programming method with compact neighbourhood algorithm for the multi-polygon mass production cutting-stock problem with rotatable polygons," International Journal of Production Economics, Elsevier, vol. 121(1), pages 148-161, September.
    11. Yizhe Yang & Bingshan Liu & Haochen Li & Xin Li & Gong Wang & Shan Li, 2023. "A nesting optimization method based on digital contour similarity matching for additive manufacturing," Journal of Intelligent Manufacturing, Springer, vol. 34(6), pages 2825-2847, August.
    12. Luiz H. Cherri & Adriana C. Cherri & Edilaine M. Soler, 2018. "Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations," Journal of Global Optimization, Springer, vol. 72(1), pages 89-107, September.
    13. Chehrazad, Sahar & Roose, Dirk & Wauters, Tony, 2022. "A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation," European Journal of Operational Research, Elsevier, vol. 300(3), pages 809-826.
    14. Drake, John H. & Kheiri, Ahmed & Özcan, Ender & Burke, Edmund K., 2020. "Recent advances in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 285(2), pages 405-428.
    15. Lastra-Díaz, Juan J. & Ortuño, M. Teresa, 2024. "Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts," European Journal of Operational Research, Elsevier, vol. 313(1), pages 69-91.
    16. López-Camacho, Eunice & Terashima-Marín, Hugo & Ochoa, Gabriela & Conant-Pablos, Santiago Enrique, 2013. "Understanding the structure of bin packing problems through principal component analysis," International Journal of Production Economics, Elsevier, vol. 145(2), pages 488-499.
    17. Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.
    18. Sato, André Kubagawa & Martins, Thiago Castro & Gomes, Antonio Miguel & Tsuzuki, Marcos Sales Guerra, 2019. "Raster penetration map applied to the irregular packing problem," European Journal of Operational Research, Elsevier, vol. 279(2), pages 657-671.
    19. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    20. Costa, M. Teresa & Gomes, A. Miguel & Oliveira, José F., 2009. "Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet," European Journal of Operational Research, Elsevier, vol. 192(1), pages 29-40, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joinma:v:28:y:2017:i:8:d:10.1007_s10845-015-1067-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.