Open AccessThe Two-Dimensional Strip Cutting Problem: Improved Results on Real-World Instances
Author(s) -
Mehdi Mrad,
Tamer G. Ali,
Ali BALMA,
Anis Gharbi,
Ali M. Al-Samhan,
M. A. LOULY
Publication year - 2021
Publication title -
the eurasia proceedings of educational and social sciences :
Language(s) - English
Resource type - Journals
ISSN - 2587-1730
DOI - 10.55549/epess.1040517
Subject(s) - mathematical optimization , mathematics , set (abstract data type) , graph , computer science , combinatorics , programming language
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.