Incremental move for strip-packing

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

7 Citas (Scopus)

Resumen

When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: every rectangle placed in a container is propped up bottom and left. While it is easy to make a rectangle BL when it is is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing incremental moves for metaheuristics or efficient complete optimization algorithms. This paper investigates the possibility of violating the BL property. Instead, we propose to maintain only the set of "maximal holes", which allows incremental additions and removals of rectangles. To validate our alternative approach, we have designed an incremental move, maintaining maximal holes, for the strip-packing problem, a variant of the famous 2D bin-packing. We have also implemented a generic metaheuristic using this move and standard greedy heuristics. Experimental results show that the approach is competitive with the best known incomplete algorithms, especially the other metaheuristics (able to escape from local minima).

Idioma originalInglés
Título de la publicación alojadaProceedings 19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007
Páginas489-496
Número de páginas8
DOI
EstadoPublicada - 2007
Publicado de forma externa
Evento19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007 - Patras, Grecia
Duración: 29 oct. 200731 oct. 2007

Serie de la publicación

NombreProceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volumen2
ISSN (versión impresa)1082-3409

Conferencia

Conferencia19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007
País/TerritorioGrecia
CiudadPatras
Período29/10/0731/10/07

Huella

Profundice en los temas de investigación de 'Incremental move for strip-packing'. En conjunto forman una huella única.

Citar esto