Generating unconstrained two‐dimensional non‐guillotine cutting patterns by a Recursive Partitioning Algorithm

Generating unconstrained two‐dimensional non‐guillotine cutting patterns by a Recursive Partitioning Algorithm

0.00 Avg rating0 Votes
Article ID: iaor2012134
Volume: 63
Issue: 2
Start Page Number: 183
End Page Number: 200
Publication Date: Feb 2012
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: combinatorial optimization, heuristics
Abstract:

In this study, a dynamic programming approach to deal with the unconstrained two‐dimensional non‐guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two‐staged and non‐staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method.

Reviews

Required fields are marked *. Your email address will not be published.