Analysis of The Relationship Between Characteristics and Hardness of Strip Packing Problem Instances

Authors

  • Edgar Alberto Oviedo Salas Universidad Autónoma de Tamaulipas
  • J. David Terán-Villanueva Universidad Autónoma de Tamaulipas
  • Salvador Ibarra-Martínez Universidad Autónoma de Tamaulipas
  • José Antonio Castan-Rocha
  • Mirna Patricia Ponce-Flores Instituto Tecnológico de Ciudad Madero
  • Julio Laria-Menchaca Universidad Autónoma de Tamaulipas
  • Mayra Guadalupe Treviño-Berrones

DOI:

https://doi.org/10.61467/2007.1558.2021.v12i2.194

Keywords:

Strip Packing, Characterization, Instance Analysis, Combinatorial problem

Abstract

The Two-Dimensional Strip Packing Problem (SPP) is an NP-Hard problem where a list of rectangular objects must be accommodated in a container to minimize the objects' total height while avoiding overlapping. It is common to use meta-heuristic algorithms to solve this problem, which produces near-optimal solutions in a reasonable time. In this paper, we analyze several characteristics of SPP instances, looking for features that define their hardness. For further development of new algorithms that make use of this knowledge.

Downloads

Published

2021-04-15

How to Cite

Oviedo Salas, E. A., Terán-Villanueva, J. D., Ibarra-Martínez, S., Castan-Rocha, J. A., Ponce-Flores, M. P., Laria-Menchaca, J., & Treviño-Berrones, M. G. (2021). Analysis of The Relationship Between Characteristics and Hardness of Strip Packing Problem Instances. International Journal of Combinatorial Optimization Problems and Informatics, 12(2), 16–24. https://doi.org/10.61467/2007.1558.2021.v12i2.194

Issue

Vol. 12 No. 2 (2021)

Section

Articles

License

Copyright (c) 2021 International Journal of Combinatorial Optimization Problems and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.