Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We study integer programming formulations for the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) considered by Rinaldi and Franz. The 2-SSCPsc arises in the context of corrugated cardboard production, which involves cutting strips of large lengths into rectangles of at most (usually) two different lengths. Because of buffer restrictions, in the 2-SSCPsc these strips must be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet. This problem is NP-hard. We present four integer programming formulations for this problem, and our computational experiments with real-life instances show that one of them has a very tight integrality gap. We propose a heuristic procedure based on this formulation and present computational experience showing that this procedure finds very good primal solutions in small running times. © 2014, Springer Science+Business Media New York.

Registro:

Documento: Artículo
Título:An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
Autor:Lucero, S.; Marenco, J.; Martínez, F.
Filiación:Computer Science Department, FCEyN, University of Buenos Aires, Int. Güiraldes y Av. Cantilo, Pabellón I, Ciudad de Buenos Aires, 1428, Argentina
Palabras clave:Corrugated cardboard; Integer programming; Sequencing; Heuristic methods; Computational experiment; Corrugated cardboards; Cutting problems; Cutting strips; Heuristic procedures; Integer programming formulations; Integrality gaps; Sequencing; Integer programming
Año:2015
Volumen:16
Número:3
Página de inicio:605
Página de fin:632
DOI: http://dx.doi.org/10.1007/s11081-014-9264-8
Título revista:Optimization and Engineering
Título revista abreviado:Optim. Eng.
ISSN:13894420
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_13894420_v16_n3_p605_Lucero

Referencias:

  • Becceneri, J., Hideki, H., Soma, N., A method for solving the minimization of the maximum number of open stacks problem within a cutting process (2004) Comput Oper Res, 31, pp. 2315-2332
  • Berinsky, H., Un modelo y algoritmo branch-and-cut para el problema del $$m$$m-anillo-estrella con capacidades (in Spanish). MSc Thesis, Computer Science Dept., FCEyN (2010) University of Buenos Aires, p. 2010
  • Bolat, A., An extended scheduling model for producing corrugated boxes (2000) Int J Prod Res, 38, pp. 1579-1599
  • Bonomo, F., Durán, G., Grippo, L., Safe, M., Partial characterizations of circular-arc graphs (2009) J Graph Theory, 61-4, pp. 289-306
  • Koch, T., Rapid mathematical programming. PhD Thesis (2004) Technische Universität Berlin, p. 2004
  • Lekkerkerker, C.G., Boland, J.C., Representation of a finite graph by a set of intervals on the real line (1962) Fundam Math, 51, pp. 45-64
  • Lins, S., Traversing trees and scheduling tasks for duplex corrugator machines (1989) Pesqui Operacional, 9, pp. 40-54
  • Linhares, A., Hideki, H., Connections between cutting-pattern sequencing, VLSI design, and flexible machines (2002) Comput Oper Res, 29, pp. 1759-1772
  • Lucero, S., Métodos basados en programación lineal entera para el problema de planificación de corrugadoras por tramos consecutivos (in Spanish). MSc Thesis (2012) Computer Science Dept., , FCEyN: University of Buenos Aires
  • Pinto, M., Yanasse, H., A heuristic to solve the cutting and sequencing integrated problem (in Portuguese) (2004) XXXVI Simpósio Brasileiro de Pesquisa Operacional, p. 2004
  • Pinto, M., Yanasse, H., Solution of the cutting and sequencing integrated problem by lagrangian relaxation (2005) XXXVII Simpósio Brasileiro de Pesquisa Operacional, p. 2005
  • Rinaldi, F., Franz, A., A two-dimensional strip cutting problem with sequencing constraint (2007) Eur J Oper Res, 183, pp. 1371-1384
  • Yanasse, H., Minimization of open orders—polynomial algorithms for some special cases (1996) Pesqui Operacional, 16-1, pp. 1-26
  • Yanasse, H., A transformation for solving a pattern sequencing problem in the wood cut industry (1997) Pesqui Operacional, 17-1, pp. 57-70
  • Yanasse, H., An exact algorithm for the tree case of the minimization of open orders problem. XXIX Simpósio Brasileiro de Pesquisa Operacional, 1997 (1997) INPE Technical Report LAC-001/97
  • Yanasse, H., On a pattern sequencing problem to minimize the maximum number of open stacks (1997) Eur J Oper Res, 100, pp. 454-463
  • Yanasse, H., Pinto, M., A lagrangian approach to solve a cutting stock problem under a particular pattern sequencing constraints (2005) V ALIO/EURO conference on combinatorial optimizatio, p. 2005
  • Yanasse, H., Lamosa, M., An integrated cutting stock and sequencing problem (2007) Eur J Oper Res, 183-3, pp. 1353-1370
  • Yanasse, H., Senne, E., The minimization of open stacks problem: a review of some properties and their use in pre-processing operations (2010) Eur J Oper Res, 203, pp. 559-567

Citas:

---------- APA ----------
Lucero, S., Marenco, J. & Martínez, F. (2015) . An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint. Optimization and Engineering, 16(3), 605-632.
http://dx.doi.org/10.1007/s11081-014-9264-8
---------- CHICAGO ----------
Lucero, S., Marenco, J., Martínez, F. "An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint" . Optimization and Engineering 16, no. 3 (2015) : 605-632.
http://dx.doi.org/10.1007/s11081-014-9264-8
---------- MLA ----------
Lucero, S., Marenco, J., Martínez, F. "An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint" . Optimization and Engineering, vol. 16, no. 3, 2015, pp. 605-632.
http://dx.doi.org/10.1007/s11081-014-9264-8
---------- VANCOUVER ----------
Lucero, S., Marenco, J., Martínez, F. An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint. Optim. Eng. 2015;16(3):605-632.
http://dx.doi.org/10.1007/s11081-014-9264-8