Title: Adaptive algorithms for Circular Cutting/packing problems

Authors: Hakim Akeb, Mhand Hifi

Addresses: Institut Superieur du Commerce, 22 bd du Fort de Vaux, 75017 Paris, France Universite de Picardie Jules Verne, UFR des Sciences, Laboratoire MIS, 33, rue Saint Leu, 80039 Amiens, France. ' Universite de Picardie Jules Verne, UFR des Sciences, Laboratoire MIS, 33, rue Saint Leu, 80039 Amiens, France

Abstract: In this paper, the Circular Cutting (CC)/packing problem is studied. Its objective is to cut/pack a set of circular pieces into a rectangular plate R of dimensions L × W. Each piece|s type i, i = 1, . . .,m, is characterised by its radius r_i and its demand b_i. This problem is solved using an adaptive algorithm that combines Beam Search (BS) and various hill-climbing strategies. Decisions at each node of the truncated tree are based on the so-called best local position using a Minimum Local-Distance Position (MLDP) rule. The computational results show, on a set of problem instances of the literature, the effectiveness of the proposed algorithm.

Keywords: approximate algorithms; beam search; BLP; best local position; circular cutting; packing; hill climbing strategies; minimum local distance.

DOI: 10.1504/IJOR.2009.027152

International Journal of Operational Research, 2009 Vol.6 No.4, pp.435 - 458

Published online: 16 Jul 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article