Problemas de otimização combinatória: uma abordagem distribuída

Abstract

The problem addressed in this paper is that of solver the combinatorial Optimization Problems, represented by 3D Bin Packing Problem that orthogonally packing a given set of box-shaped items into the minimum number of three-dimensional rectangular and equal bins. The problem is NP-hard in the strong sense and extremely difficult to be solved in the practice. We present a parallel computer algorithm to solver the problem. Two metaheuristics went used in the parallel model, AGEE and HPEE. AGEE is based in the genetics algorithms while HPEE is a sophisticated heuristics that avoids to join in local minimum, both algorithms generating diversification on the search of the feasible solution. In the model, we also use an heuristic HVEE which make a intensification in the best current solution of each iteration. We used criterions to pack every items with static stability. Extensive computational experiments are reported for instances with up to 90 items, and the results are compared with those obtained from the literature.