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

Authors : Mehdi Mrad, Tamer G. Ali, Ali Balma, Anis Gharbi, Ali Samhan, M. A. Louly

Pages : 1-10

Doi:10.55549/epess.1040517

View : 16 | Download : 7

Publication Date : 2021-12-31

Article Type : Other

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.
Keywords : Integer programming, Arc-flow formulation, Strip cutting problem, Graph compression.