Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1061.90095
Hifi, Mhand; M'Hallah, Rym
Approximate algorithms for constrained circular cutting problems. (English)
[J] Comput. Oper. Res. 31, No. 5, 675-694 (2004). ISSN 0305-0548

Summary: 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 with radii $r_i$, $i=1,\dots ,n$. We solve the constrained circular problem, where $d_i$ 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 (Studia. Inform. Univ. 2 (1), 33 (2002)) 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.

MSC 2000:: *90C27 Combinatorial programming
90C59 Approximation methods and heuristics

Keywords: best local position; circular cutting problem; combinatorial optimization; genetic algorithms; heuristics

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]