The Two-Dimensional Strip Cutting Problem: Improved Results on Real-World Instances

36 26

Authors

  • Mehdi MRAD King Saud University
  • Tamer G. ALI King Saud University
  • Ali BALMA Ecole Nationale Supérieure d’Ingénieurs de Tunis
  • Anis GHARBI King Saud University
  • Ali SAMHAN King Saud University
  • M. A. LOULY Ecole Supérieure Polytechnique Mauritanie

DOI:

https://doi.org/10.55549/epess.1040517

Keywords:

Integer programming, Arc-flow formulation, Strip cutting problem, Graph compression.

Abstract

Cutting and packing problems arise in various industrial settings such as production of metal, glass sheets, papers, etc. The demand of items should be met while minimizing loss of waste material. One of the most known as a contemporary problem in field of operations research is the two-dimensional strip cutting problem. A set of m rectangular items is to be cut from a two-dimensional strip of width W and infinite height. Each item i (i=1,2,…,m) has a width wi, a height hi, and a demand di. The objective is to determine how to cut the demanded items using the minimum height of strip and meet all the demands, while respecting the two stages of guillotine cuts. We address the arc-flow formulation for this NP-hard problem. A graph compression method is proposed and it is shown that substantially better results are achieved in obtaining optimal or near-optimal solutions of real-world instances.

Downloads

Published

2021-12-31

How to Cite

MRAD, M., G. ALI, T., BALMA, A., GHARBI, A., SAMHAN, A., & LOULY, M. A. (2021). The Two-Dimensional Strip Cutting Problem: Improved Results on Real-World Instances. The Eurasia Proceedings of Educational and Social Sciences, 22, 1–10. https://doi.org/10.55549/epess.1040517

Issue

Section

Articles