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

New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers

  • Published:
Journal of the Operational Research Society

Abstract

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Arenales M, Cherri A, Nascimento DN and Vianna A (2015). A new mathematical model for the cutting stock/leftover problem. Pesquisa Operacional 35(3):509–522.

    Article  Google Scholar 

  • Beeker KH and Appa G (2015). A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem. Journal of the Operational Research Society 66(8):1297–1311.

    Article  Google Scholar 

  • Belov G and Scheithauer G (2002). A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. European Journal of Operational Research 141(2):274–294.

    Article  Google Scholar 

  • Belov G and Scheithauer G (2006). A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171(1):85–106.

    Article  Google Scholar 

  • Belov G and Scheithauer G (2007). Setup and open-stacks minimization in one-dimensional stock cutting. INFORMS Journal on Computing 19(1):27–35.

    Article  Google Scholar 

  • Cherri AC, Arenales MN and Yanasse HH (2009). The one dimensional cutting stock problem with usable leftover—A heuristic approach. European Journal of Operational Research 196(3):897–908.

    Article  Google Scholar 

  • Cherri AC, Arenales MN and Yanasse HH (2013). The usable leftover one-dimensional cutting stock problem—A priority-in-use heuristic. International Transactions in Operational Research 20(2):189–199.

    Article  Google Scholar 

  • Cui Y (2012). A CAM system for one-dimensional stock cutting. Advances in Engineering Software 47(1):7–16.

    Article  Google Scholar 

  • Cui Y and Yang Y (2010). A heuristic for the one-dimensional cutting stock problem with usable leftover. European Journal of Operational Research 204(2):245–250.

    Article  Google Scholar 

  • Cui Y-P, Cui Y, Tang T and Hu W (2015). Heuristic for constrained two-dimensional three-staged patterns. Journal of the Operational Research Society 66(4):647–656.

    Article  Google Scholar 

  • Foerster H and Wäscher G (2000). Pattern reduction in one dimensional cutting stock problems. International Journal of Production Research 38(7):1657–1676.

    Article  Google Scholar 

  • Gilmore PC and Gomory RE (1963). A linear programming approach to the cutting-stock problem (Part II). Operations Research 11(6):863–887.

    Article  Google Scholar 

  • Gradisar M, Kljajic M and Resinovic C (1999a). A sequential heuristic procedure for one-dimensional cutting. European Journal of Operational Research 114(3):557–568.

    Article  Google Scholar 

  • Gradisar M, Resinovic C and Kljajic M (1999b). A hybrid approach for optimization of one-dimensional cutting. European Journal of Operational Research 119(3):719–728.

    Article  Google Scholar 

  • Gradisar M and Trkman P (2005). A combined approach to the solution to the general one-dimensional cutting stock problem. Computers & Operations Research 32(7):1793–1807.

    Article  Google Scholar 

  • Kellerer H, Pferschy U and Pisinger D (2004). Knapsack Problems. Berlin: Springer.

    Book  Google Scholar 

  • Moreira de Carvalho MA and Soma NY (2015). A breadth-first search applied to the minimization of the open stacks. Journal of the Operational Research Society 66(6):936–946.

    Article  Google Scholar 

  • Scheithauer G (1991). A note on handling residual lengths. Optimization 22(3):461–466.

    Article  Google Scholar 

  • Scheithauer G and Terno J (1995). The modified integer round-up property of the one-dimensional cutting stock problem. European Journal of Operational Research 84(3):562–571.

    Article  Google Scholar 

  • Valerio de Carvalho JMV (2005). Using extra dual cuts to accelerate column generation. INFORMS Journal on Computing 17(2):175–182.

    Article  Google Scholar 

  • Yanasse HH and Limeira MS (2006). A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Computers & Operations Research 33(9):2744–2756.

    Article  Google Scholar 

Download references

Acknowledgments

This research is part of Projects 71371058 and 61363026 supported by the National Natural Science Foundation of China.

Author information

Authors and Affiliations

  1. College of Computer and Electronic Information, Guangxi University, Nanning, 530004, China

    Yaodong Cui & Yan Chen

  2. Department of Mathematics, University of Portsmouth, Portsmouth, PO1 3HF, UK

    Xiang Song

  3. School of Business Administration, South China University of Technology, Guangzhou, 510640, China

    Yan Chen & Yi-Ping Cui

Authors
  1. Yaodong Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiang Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yan Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yi-Ping Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yaodong Cui.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cui, Y., Song, X., Chen, Y. et al. New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers. J Oper Res Soc 68, 269–280 (2017). https://doi.org/10.1057/s41274-016-0098-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/s41274-016-0098-y

Keywords

Search

Navigation