Bin-packing by simulated annealing

AbstractThe process of gradually settling a combinatorial system into configurations of globally minimum energy has variously been called simulated annealing, statistical cooling, and so on. In the past, very large combinatorial optimization problems have been solved using this technique. It has also been shown that this method is effective in obtaining close-to-optimal solutions for problems known to be NP complete. Further, this technique is applicable to a whole class of problems that satisfy a few requirements.The purpose of this paper is to illustrate an efficient version of the simulated annealing method as applied to a variant of the bin-packing problem. The computational complexity of the method is linear in input size similar to various well-known heuristic methods for the problem. The solutions obtained, however, are much better than any of the heuristic methods. The particular variant of the bin-packing problem we consider has several practical applications such as static task allocation in process scheduling and batch processing. At the time of this writing, we have not yet seen a stochastic solution to the bin-packing problem in the literature.One of the distinguishing features of our research is the high quality of solutions obtained by our method. Extensive simulation experiments we have carried out show that the solutions obtained by the stochastic method show a significant improvement over those obtained by any of the well-known heuristic methods