A stochastic approach to the bin-packing problem Conference

Rao, RL, Iyengar, SS. (1994). A stochastic approach to the bin-packing problem . Part F129433 261-265. 10.1145/326619.326742

cited authors

  • Rao, RL; Iyengar, SS

authors

abstract

  • The process of gradually settling a combinatorial system into configurations of globally minimum energy has variously been called simulated annealing, statistical cooling, and so on. 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. 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.

publication date

  • April 6, 1994

Digital Object Identifier (DOI)

start page

  • 261

end page

  • 265

volume

  • Part F129433