A best-first branch-and-bound algorithm for orthogonal rectangular packing problems

✍ Scribed by Mhand Hifi; Rachid Ouafi

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 294 KB
• Volume: 5
• Category: Article
• ISSN: 0969-6016
• DOI: 10.1016/s0969-6016(98)00026-4

✦ Synopsis

In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing ®nal rectangle. We present ®rst a best-®rst branch-and-bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces highquality solutions within small computational time.