Approximate algorithms for constrained circular cutting problems

Approximate algorithms for constrained circular cutting problems

0.00 Avg rating0 Votes
Article ID: iaor20043142
Country: United Kingdom
Volume: 31
Issue: 5
Start Page Number: 675
End Page Number: 694
Publication Date: Apr 2004
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

In this paper, we study the problem of cutting a rectangular plate R of dimensions (L,W) into as many circular pieces as possible. The circular pieces are of n different types of radii ri,i = 1,…,n. We solve the constrained circular problem, where di the maximum demand for piece type i is specified, using two heuristics: a constructive procedure-based heuristic and a genetic algorithm-based heuristic. Both of these approaches search for a good ordering of the pieces and use an adaptation of the best local position procedure to find the “best” layout of this ordered set. This positioning procedure is specifically tailored to circular cutting problems. It acts, for constrained problems, as one of the mutation operators of the genetic algorithm. We compare the performance of both proposed approaches to that of existing approximate and exact algorithms on several problem instances taken from the literature. The computational results show that the proposed approaches produce high-quality solutions within reasonable computational times. The genetic algorithm-based heuristic is easily parallelizable; one of its important features to be investigated in the near future.

Reviews

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