Skip to main content
SpringerLink
Log in

New integer programming formulations and an exact algorithm for the ordered cutting stock problem

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

Apart from trim loss minimization, there are many other issues concerning cutting processes that arise in real production systems. One of these is related to the number of stacks that need to be opened near the cutting machines. Many researchers have worked in the last years on cutting stock problems with additional constraints on the number of open stacks. In this paper, we address a related problem: the Ordered Cutting Stock Problem (OCSP). In this case, a stack is opened for every new client's order, and it is closed only when all the items of that order are cut. The OSCP has been introduced recently in the literature. Our aim is to provide further insight into this problem. This paper describes three new integer programming formulations for solving it, and an exact algorithm based on column generation, branch-and-bound and cutting planes. We report on computational experiments on a set of random instances. The results show that good lower bounds can be computed quickly, and that optimal solutions can be found in a reasonable amount of time.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5

Similar content being viewed by others

References

  • Alves C (2005). Cutting and packing: Problems, models and exact algorithms. PhD thesis, University of Minho.

  • Alves C and Valério de Carvalho JM (2006). A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput Opl Res, doi: 10.1016/j.cor.2006.08.014.

  • Alves C and Valério de Carvalho JM (2007). Accelerating column generation for variable sized bin-packing problems. Eur J Opl Res 183: 1333–1352.

    Article  Google Scholar 

  • Becceneri J, Yanasse H and Soma N (2004). A method for solving the minimization of the maximum number of open stacks problem within a cutting process. Comput Opl Res 31: 2315–2332.

    Article  Google Scholar 

  • Belov G (2003). Problems, models and algorithms in one- and two-dimensional cutting. PhD thesis, University of Dresden.

  • Chen C, Hart S and Tham W (1996). A simulated annealing heuristic for the one-dimensional cutting stock problem. Eur J Opl Res 93: 522–535.

    Article  Google Scholar 

  • Farley A (1990). A note on bounding a class of linear programming problems, including cutting stock problems. Opns Res 38: 922–923.

    Article  Google Scholar 

  • Fink A and Voß S (1999). Applications of modern heuristic search methods to pattern sequencing problems. Comput Opl Res 26: 17–34.

    Article  Google Scholar 

  • Foerster H and Waescher G (2000). Pattern reduction in one-dimensional cutting stock problems. Int J Prod Res 38: 1657–1676.

    Article  Google Scholar 

  • Gilmore P and Gomory R (1961). A linear programming approach to the cutting stock problem. Opns Res 9: 849–859.

    Article  Google Scholar 

  • Gilmore P and Gomory R (1963). A linear programming approach to the cutting stock problem: Part II. Opns Res 11: 863–888.

    Article  Google Scholar 

  • Haessler R (1971). A heuristic programming solution to a nonlinear cutting stock problem. Mngt Sci 17: 793–802.

    Article  Google Scholar 

  • ILOG (1999). CPLEX 6.5 User's Manual. 9, rue de Verdun, BP85, F-92453, Gentilly, France.

  • Johnson M, Rennick C and Zak E (1999). One-dimensional cutting stock problem in just-in-time environment. Pesquisa Operacional 19: 145–158.

    Google Scholar 

  • Linhares A and Yanasse H (2002). Connections between cutting-pattern sequencing, VLSI design, and flexible machines. Comput Opl Res 29: 1759–1772.

    Article  Google Scholar 

  • Luebbecke M and Desrosiers J (2005). Selected topics in column generation. Opns Res 53: 1007–1023.

    Article  Google Scholar 

  • Madsen O (1988). An application of travelling-salesman routines to solve pattern-allocation problems in the glass industry. J Opl Res Soc 39: 249–256.

    Article  Google Scholar 

  • Nemhauser G and Wolsey L (1988). Integer and Combinatorial Optimization. John Wiley & Sons: New York.

    Book  Google Scholar 

  • Ragsdale C and Zobel C (2004). The ordered cutting stock problem. Decis Sci 35: 83–100.

    Article  Google Scholar 

  • Schreck H (2002). A sequence problem in practical trim optimization. In: Proceedings of the 16th triennial conference of the International Federation of Operational Research Societies. IFORS: Edinburgh, pp. 121.

    Google Scholar 

  • Umetani S, Yagiura M and Ibaraki T (2003). One-dimensional cutting stock problem to minimize the number of different patterns. Eur J Opl Res 146: 388–402.

    Article  Google Scholar 

  • Valério de Carvalho JM (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Ann Opns Res 86: 629–659.

    Article  Google Scholar 

  • Vanderbeck F (2000). Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Opns Res 48: 915–926.

    Article  Google Scholar 

  • Villeneuve D, Desrosiers J, Luebbecke M and Soumis F (2005). On compact formulations for integer programs solved by column generation. Ann Opns Res 139: 375–388.

    Article  Google Scholar 

  • Yanasse H (1997). On a pattern sequencing problem to minimize the maximum number of open stacks. Eur J Opl Res 100: 454–463.

    Article  Google Scholar 

Download references

Acknowledgements

This work was partially supported by the portuguese Science and Technology Foundation (Projecto POS C/57203/EIA/2004) and by the Algoritmi Research Center of the University of Minho, and was developed in the Industrial and Systems Engineering Group.

Author information

Authors and Affiliations

  1. Universidade do Minho, Braga, Portugal

    C Alves & J M Valério de Carvalho

Authors
  1. C Alves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J M Valério de Carvalho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C Alves.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alves, C., Valério de Carvalho, J. New integer programming formulations and an exact algorithm for the ordered cutting stock problem. J Oper Res Soc 59, 1520–1531 (2008). https://doi.org/10.1057/palgrave.jors.2602494

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2602494

Keywords

Search

Navigation