Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem

详细信息    查看全文

• 作者：Kelly Cristina Poldi ; Silvio Alexandre de Araujo
• 关键词：Cutting stock problem ; Multiperiod ; Mathematical models ; Residual heuristic
• 刊名：Annals of Operations Research
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：238
• 期：1-2
• 页码：497-520
• 全文大小：512 KB
• 参考文献：Alem, D. J., & Morabito, R. (2012). Production planning in furniture settings via robust optimization. Computers & Operations Research, 39, 139–150.CrossRef
  Alem, D. J., & Morabito, R. (2013). Risk-averse two-stage stochastic programs in furniture plants. OR Spectrum, 35, 773–806.CrossRef
  Aloisio, A., Arbib, C., & Marinelli, F. (2009). On LP relaxations for the pattern minimization problem. Networks, 57, 247–253.CrossRef
  Arbib, C., & Marinelli, F. (2005). Integrating process optimization and inventory planning in cutting-stock with skiving option: An optimization model and its application. European Journal of Operational Research, 163, 617–630.CrossRef
  Arbib, C., & Marinelli, F. (2014). On cutting stock with due dates. Omega, 46, 11–20.CrossRef
  Beasley, J. E. (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33, 49–64.CrossRef
  de Araujo, S. A., Arenales, M. N., & Clark, A. R. (2008). Lot-sizing and furnace scheduling in small foundries. Computers & Operations Research, 35, 916–932.CrossRef
  de Araujo, S. A., & Clark, R. (2013). A priori reformulations for joint rolling-horizon scheduling of materials processing and lot-sizing problem. Computers & Industrial Engineering, 65, 577–585.CrossRef
  de Araujo, S. A., Poldi, K. C., & Smith, J. (2014). A genetic algorithm for the one-dimensional cutting stock problem with setups. Pesquisa Operacional, 34, 165–187.CrossRef
  Diegel, A., Chetty, M., Van Schalkwyk, S. & Naidoo, S. (1996). Setup combining in the trim-loss problem 3 to 2 and 2 to 1. Durban: Business Administration, University of Natal. Working Paper.
  Foerster, H., & Wäscher, G. (2000). Pattern reduction in one-dimensional cutting stock problems. International Journal of Production Research, 38(7), 1657–1676.CrossRef
  Gau, T., & Wäscher, G. (1995). CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European Journal of Operational Research, 84(3), 572–579.CrossRef
  Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting stock problem. Operations Research, 9, 848–859.CrossRef
  Gilmore, P. C., & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem-Part II. Operations Research, 11, 863–888.CrossRef
  Gilmore, P. C., & Gomory, R. E. (1965). Multi-stage cutting stock problems of two and more dimensions. Operations Research, 13, 94–120.CrossRef
  Gramani, M. C. N., & França, P. M. (2006). The combined cutting stock and lot sizing problem in industrial process. European Journal of Operational Research, 74, 509–521.CrossRef
  Gramani, M. C. N., França, P. M., & Arenales, M. N. (2009). A Lagrangian relaxation approach to a coupled lot-sizing and cutting stock problem. International Journal of Production Economics, 119, 219–227.CrossRef
  Gramani, M. C. N., França, P. M., & Arenales, M. N. (2011). A linear optimization approach to the combined production planning model. Journal of the Franklin Institute, 348, 1523–1536.CrossRef
  Henn, S., & Wäscher, G. (2013). Extensions of cutting problems: Setups. Pesquisa Operacional, 33(2), 133–162.CrossRef
  Johnston, R. E., & Sadinlija, E. (2004). A new model for complete solutions to one-dimensional cutting stock problems. European Journal of Operational Research, 153, 176–183.CrossRef
  Li, S. (1996). Multi-job cutting stock problem with due-dates and release-dates. Journal of the Operational Research Society, 47, 490–510.CrossRef
  Malik, M. M., Qiu, M. & Taplin J. (2009). An integrated approach to the lot sizing and cutting stock problems. In Proceedings of the 2009 International Conference on Industrial Engineering and Engineering Management, IEEM 2009, Hong Kong, China, pp. 1111–1115.
  Nemhauser, G., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley.CrossRef
  Nonas, S. L., & Thorstenson, A. (2008). Solving a combined cutting-stock and lot-sizing problem with a column generating procedure. Computers & Operations Research, 35, 3371–3392.CrossRef
  Pinho de Sousa, J., & Wolsey, L. A. (1992). A time-indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 54, 353–367.CrossRef
  Poldi, K. C. (2007). O problema de corte de estoque multiperíodo. PhD Thesis, Instituto de Ciências Matemáticas e de Computação ICMC/USP – Universidade de São Paulo.
  Poldi, K. C., & Arenales, M. N. (2009). Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Computers & Operations Research, 36, 2074–2081.CrossRef
  Poldi, K. C., & Arenales, M. N. (2010). O problema de corte de estoque unidimensional multiperíodo. Pesquisa Operacional, 30, 153–174.CrossRef
  Poltroniere, S. C., Poldi, K. C., Toledo, F. M. B., & Arenales, M. N. (2008). A coupling cutting stock-lot sizing problem in the paper industry. Annals of Operations Research, 157, 91–104.CrossRef
  Reinertsen, H., & Vossen, T. W. M. (2010). The one-dimensional cutting stock problem with due-dates. European Journal of Operational Research, 201, 701–711.
  Silva, E., Alvelos, F., & Valério de Carvalho, J. M. (2014). Integrating two-dimensional cutting stock and lot sizing problems. Journal of the Operational Research Society, 65, 108–123.
  Suliman, S. M. A. (2012). An algorithm for solving lot sizing and cutting stock problem within aluminum fabrication industry. In Proceedings of the 2012 International Conference on Industrial Engineering and Operations Management, Bali, Indonesia, pp. 783–793.
  Trigeiro, W. W., Thomas, L. J., & McClain, J. O. (1989). Capacitated lot sizing with setup times. Management Science, 35(3), 353–366.CrossRef
  Valério de Carvalho, J. M. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86, 629–659.CrossRef
  Valério de Carvalho, J. M. (2002). LP models for bin packing and cutting stock problems. European Journal of Operational Research, 144, 253–273.CrossRef
  Vanderbeck, F. (2000). Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Operations Research, 48, 915–926.CrossRef
  Vanzela, M., Rangel, M. S., & Araujo, S. A. (2013). The integrated lot sizing and cutting stock problem in a furniture factory. In Annals of the 11th IFAC Workshop on Intelligent Manufacturing Systems, São Paulo, Brazil.
  Yanasse, H. H., & Limeira, M. S. (2006). A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Computer & Operations Research, 33, 2744–2756.CrossRef
  
• 作者单位：Kelly Cristina Poldi (1)
  Silvio Alexandre de Araujo (2)
  
  1. Instituto de Matemática, Estatística e Computação Científica-IMECC, Universidade Estadual de Campinas-UNICAMP, Rua Sergio Buarque de Holanda, 651, Campinas, SP, 13083-859, Brazil
  2. Departamento de Matemática Aplicada-DMAp, Universidade Estadual Paulista-UNESP, Rua Cristóvão Colombo, 2265, São José do Rio Preto, SP, 15054-000, Brazil
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Combinatorics
  Theory of Computation
  
• 出版者：Springer Netherlands
• ISSN：1572-9338

文摘

The multiperiod cutting stock problem arises in the production planning and programming of many industries that have the cutting process as an important stage. Ordered items are required in different periods of a finite planning horizon. It is possible to bring forward or not the production of items. Unused inventory in a certain period becomes available for the next period, all together with new inventory which may come to be acquired in the market. Based on mixed integer optimization models from the literature, extensions are proposed to deal with the multiperiod case and a residual heuristic is used. Computational experiments showed that effective gains can be obtained when comparing multiperiod models with the lot for lot solution, which is typically used in practice. Most of the instances are solved satisfactorily with a high performance optimization package and the heuristic method is used for solving the hard instances.