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

  • Edgar Alberto Oviedo Salas Universidad Autónoma de Tamaulipas https://orcid.org/
  • 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
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.

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. Retrieved from https://ijcopi.org/ojs/article/view/194
Issue
Vol. 12 No. 2 (2021)
Section
Articles

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.