Solving Irregular Rotational Knapsack Problems

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 (SA), which is in-spired on the physic-chemical process that takes 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 SA controls: the rotation and the placement. For each non–placed item