[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Pattern Combination Based Approach to Two-Dimensional Cutting Stock Problem

  • Conference paper
Advances in Natural Computation (ICNC 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3612))

Included in the following conference series:

  • 1774 Accesses

Abstract

A new approach for dealing with a huge number of cutting pattern combinations encountered in two-dimensional Cutting Stock Problem (CSP) is described. Firstly, cutting patterns are produced according to a novel cutting method LF(Lease Fit) algorithm which can effectively cuts a sequence of small rectangular pieces from a big stock, heuristically maximizing the stock’s utilization ratio. Then Genetic Algorithm (GA) is applied to search for a near optimal solution which consists of many patterns namely a pattern combination. To evaluate the combination’s fitness, LP (Linear Programming) algorithm is used in polynomial time without bringing about much error. The performance and efficiency are justified by numerical experiments.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Valerio de Carvalho, J.M.: LP models for bin packing and cutting stock problems. Journal of Operations Research 141, 253–273 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Journal of Operatiosns Research 9, 849–859 (1961)

    Article  MATH  MathSciNet  Google Scholar 

  3. Yeung, L.H.W., Tang, W.K.S.: A hybrid genetic approach for garment cutting in clothing industry. IEEE Transactions on Industrial Electronics 50(3), 449–455 (2003)

    Article  Google Scholar 

  4. Leung, T.W., Yung, C.H., Troutt, M.D.: Application of genetic search and simulate annealing to the two-dimensional non-guillotine cutting stock problem. Computers and Industrial Engineering 40, 201–214 (2001)

    Article  Google Scholar 

  5. Suliman, S.M.A.: Pattern generating procedure for the cutting stock problem. Journal of Operations Research 74, 293–301 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Shanghai Jiao Tong University, Shanghai, China

    Jinming Wan, Yadong Wu & Hongwei Dai

Authors
  1. Jinming Wan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yadong Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongwei Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Electrical and Electronic Engineering, Nanyang Technological University, Block S1, Nanyang Avenue, 639798, Singapore

    Lipo Wang

  2. School of Software, Sun Yat-Sen University, 510275, Guangzhou, China

    Ke Chen

  3. School of Computer Engineering, Nanyang Technological University, BLK N4, 2b-39, Nanyang Avenue, 639798, Singapore

    Yew Soon Ong

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Wan, J., Wu, Y., Dai, H. (2005). A Pattern Combination Based Approach to Two-Dimensional Cutting Stock Problem. In: Wang, L., Chen, K., Ong, Y.S. (eds) Advances in Natural Computation. ICNC 2005. Lecture Notes in Computer Science, vol 3612. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11539902_39

Download citation

  • DOI: https://doi.org/10.1007/11539902_39

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28320-1

  • Online ISBN: 978-3-540-31863-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics