IRREGULAR ROTATIONAL PLACEMENT OF SHAPES OVER NON–CONVEX CONTAINERS WITH FIXED DIMENSIONS

This work deals with the problem of minimize the waste of space that occurs on a placement of a set of bi-dimensional items inside a bi-dimensional container with fixed dimensions. This problem is approached with an heuristic based on Simulated Annealing, which is inspired on the physic-chemical process that take place during the recrystallization of a metal. Traditional “external penalization” techniques are avoided through the application of no–fit polygons, that represents collision-free areas for each items before its placement. That gives to the proposed process a more universal character, as external penalization is based on empiric parameters of great influence on the optimization performance. The simulated annealing controls: the rotation and the placement. For each non–placed items a limited depth binary search is performed to find a scale factor that when applied to the items, would allow it to be fitted on the container. The proposed process is suited for non-convex items and containers, and can be easily adapted for related problems, such as container size minimization. Some results are shown with irregular items, non–convex items and containers.