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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_13894420_v16_n3_p605_Lucero |
| Aporte de: |
| id |
todo:paper_13894420_v16_n3_p605_Lucero |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_13894420_v16_n3_p605_Lucero2023-10-03T16:12:43Z An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint Lucero, S. Marenco, J. Martínez, F. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Lucero, S. Marenco, J. Martínez, F. 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. |
| format |
JOUR |
| author |
Lucero, S. Marenco, J. Martínez, F. |
| author_facet |
Lucero, S. Marenco, J. Martínez, F. |
| author_sort |
Lucero, 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_13894420_v16_n3_p605_Lucero |
| work_keys_str_mv |
AT luceros anintegerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint AT marencoj anintegerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint AT martinezf anintegerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint AT luceros integerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint AT marencoj integerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint AT martinezf integerprogrammingapproachforthe2schemesstripcuttingproblemwithasequencingconstraint |
| _version_ |
1807323782604390400 |