Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers

In the two-dimensional guillotine cutting-stock problem, the objective is to minimize the number of large plates used to cut a list of small rectangles. We consider a variant of this problem, which arises in glass industry when different bills of order (or batches) are considered consecutively. For...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	François Clautiaux, Ruslan Sadykov, François Vanderbeck, Quentin Viaud
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	90-08 90B30 90B80 90C27 90C39 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/6537fed784134269ab6d6f6bb13a340e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6537fed784134269ab6d6f6bb13a340e
record_format	dspace
spelling	oai:doaj.org-article:6537fed784134269ab6d6f6bb13a340e2021-12-02T05:01:12ZPattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers2192-440610.1007/s13675-019-00113-9https://doaj.org/article/6537fed784134269ab6d6f6bb13a340e2019-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001180https://doaj.org/toc/2192-4406In the two-dimensional guillotine cutting-stock problem, the objective is to minimize the number of large plates used to cut a list of small rectangles. We consider a variant of this problem, which arises in glass industry when different bills of order (or batches) are considered consecutively. For practical organization reasons, leftovers are not reused, except the large one obtained in the last cutting pattern of a batch, which can be reused for the next batch. The problem can be decomposed into an independent problem for each batch. In this paper, we focus on the one-batch problem, the objective of which is to minimize the total width of the cutting patterns used. We propose a diving heuristic based on column generation, in which the pricing problem is solved using dynamic programming (DP). This DP generates so-called non-proper columns, i.e. cutting patterns that cannot participate in a feasible integer solution of the problem. We show how to adapt the standard diving heuristic to this “non-proper” case while keeping its effectiveness. We also introduce the partial enumeration technique, which is designed to reduce the number of non-proper patterns in the solution space of the dynamic program. This technique strengthens the lower bounds obtained by column generation and improves the quality of the solutions found by the diving heuristic. Computational results are reported and compared on classical benchmarks from the literature as well as on new instances inspired from glass industry data. According to these results, variants of the proposed diving heuristic outperform constructive and evolutionary heuristics.François ClautiauxRuslan SadykovFrançois VanderbeckQuentin ViaudElsevierarticle90-0890B3090B8090C2790C39Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 3, Pp 265-297 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-08 90B30 90B80 90C27 90C39 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-08 90B30 90B80 90C27 90C39 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 François Clautiaux Ruslan Sadykov François Vanderbeck Quentin Viaud Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
description	In the two-dimensional guillotine cutting-stock problem, the objective is to minimize the number of large plates used to cut a list of small rectangles. We consider a variant of this problem, which arises in glass industry when different bills of order (or batches) are considered consecutively. For practical organization reasons, leftovers are not reused, except the large one obtained in the last cutting pattern of a batch, which can be reused for the next batch. The problem can be decomposed into an independent problem for each batch. In this paper, we focus on the one-batch problem, the objective of which is to minimize the total width of the cutting patterns used. We propose a diving heuristic based on column generation, in which the pricing problem is solved using dynamic programming (DP). This DP generates so-called non-proper columns, i.e. cutting patterns that cannot participate in a feasible integer solution of the problem. We show how to adapt the standard diving heuristic to this “non-proper” case while keeping its effectiveness. We also introduce the partial enumeration technique, which is designed to reduce the number of non-proper patterns in the solution space of the dynamic program. This technique strengthens the lower bounds obtained by column generation and improves the quality of the solutions found by the diving heuristic. Computational results are reported and compared on classical benchmarks from the literature as well as on new instances inspired from glass industry data. According to these results, variants of the proposed diving heuristic outperform constructive and evolutionary heuristics.
format	article
author	François Clautiaux Ruslan Sadykov François Vanderbeck Quentin Viaud
author_facet	François Clautiaux Ruslan Sadykov François Vanderbeck Quentin Viaud
author_sort	François Clautiaux
title	Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
title_short	Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
title_full	Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
title_fullStr	Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
title_full_unstemmed	Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
title_sort	pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/6537fed784134269ab6d6f6bb13a340e
work_keys_str_mv	AT francoisclautiaux patternbaseddivingheuristicsforatwodimensionalguillotinecuttingstockproblemwithleftovers AT ruslansadykov patternbaseddivingheuristicsforatwodimensionalguillotinecuttingstockproblemwithleftovers AT francoisvanderbeck patternbaseddivingheuristicsforatwodimensionalguillotinecuttingstockproblemwithleftovers AT quentinviaud patternbaseddivingheuristicsforatwodimensionalguillotinecuttingstockproblemwithleftovers
_version_	1718400831696404480

Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers

Ejemplares similares