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

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.
Cover

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

Vol. 22 (2021)

Section

Articles

License

Copyright (c) 2021 The Eurasia Proceedings of Educational and Social Sciences

Creative Commons License

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

The articles may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Authors alone are responsible for the contents of their articles. The journal owns the copyright of the articles. The publisher shall not be liable for any loss, actions, claims, proceedings, demand, or costs or damages whatsoever or howsoever caused arising directly or indirectly in connection with or arising out of the use of the research material. All authors are requested to disclose any actual or potential conflict of interest including any financial, personal or other relationships with other people or organizations regarding the submitted work.