An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint

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...

Descripción completa

Detalles Bibliográficos
Autor principal: Martínez, Federico Nicolás
Publicado: 2015
Materias:
Corrugated cardboard
Integer programming
Sequencing
Heuristic methods
Computational experiment
Corrugated cardboards
Cutting problems
Cutting strips
Heuristic procedures
Integer programming formulations
Integrality gaps
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_13894420_v16_n3_p605_Lucero
http://hdl.handle.net/20.500.12110/paper_13894420_v16_n3_p605_Lucero
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_13894420_v16_n3_p605_Lucero
record_format dspace
spelling paper:paper_13894420_v16_n3_p605_Lucero2023-06-08T16:13:08Z An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint Martínez, Federico Nicolás 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 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. Fil:Martínez, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_13894420_v16_n3_p605_Lucero http://hdl.handle.net/20.500.12110/paper_13894420_v16_n3_p605_Lucero
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Martínez, Federico Nicolás
An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
topic_facet 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
description 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.
author Martínez, Federico Nicolás
author_facet Martínez, Federico Nicolás
author_sort Martínez, Federico Nicolás
title An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
title_short An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
title_full An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
title_fullStr An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
title_full_unstemmed An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
title_sort integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_13894420_v16_n3_p605_Lucero
http://hdl.handle.net/20.500.12110/paper_13894420_v16_n3_p605_Lucero
work_keys_str_mv AT martinezfedericonicolas anintegerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint
AT martinezfedericonicolas integerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint
_version_ 1768545846186475520

Ejemplares similares