Thank's for your help miss... are any other method to reduce NP-Hard bin packing problem until now?

Dear Terry:

Irregular confiration bBin packing problem is a generalization of the the irregular configuration pieces  on surfaces, by this it is necessary firstly to work on the surfaces a afterward on the sapace.

Irregular configuration pieces distribution and cutting on the foil could be solved by Searching by Random Exploration of the Extreme of a Function of a  Variable Code, following way

In this case, instead of making evolve a variable code, several codes are simultaneously made evolving. As by the previous algorithm random partitions are made but for each combination of the internal points of the partitions the corresponding solutions by each variable code is decoded and selected the component that belongs together with the combination having the best objective function value. It  is eliminated the subinterval of each variable code that doesn't contain the component of the best solution among the 2n evaluated ones. In each step the current variation interval of any variable code that fulfill the condition that it is equal or less than 2 is totally opened up.  This algorithm wil be called REEVCA algorithm.

     The same as for the previous algortihm, a solutions population is created and upgraded, composed in this case by concrete values of n codes and of the objective function value. The objective function value of the population's worst solution is compared with the corresponding value of each solution generated in the search process and it is substituted, in the case when the recently generated one improves it. 

     In the figure 28 (see Analysis and Sinthesys of Enginerring Systems, that could be downloaded from my researchgate personal profil) n the  the procedure of generation of codes combinations is illustrated for the particular case of two variable codes. For each generated and decoded solutions combination the objective function is calculated. The generated codes combination is determined to which  the smallest value of this function it is associated and the search subinterval of each variable code is eliminated that doesn't contain the component of the solution with this smaller value. The same as for the previous algorithm, the process stops lapsed a number of successive iterations without improving the solutions quality.   

 this task is a part of the general irregular pieces fabrication on foils task, presented in the example 7 of this work in its integration to the pieces design, technologies generation and production planning.

     Conglomerates of pieces, restricted by the limits of the proper foil or for the fact of not existence of new pieces to locate are created and evaluated.  When being coupled two pieces a conglomerate it is settled down, which is considered as a new piece for it later coupling with another, from the set of pieces candidates to conform it vicinity. In the figure 29 the process of creation of three pieces conglomerate is illustrated.                

    A bicriterial objective function is used that represents a commitment among the quality of the pieces coupling and the quality of its insertion on the foil, with the particularity that the weight of the second indicator increases with the increment of the dimensions of the conglomerate.

For the whole solution codes variation interval (serial numbers of the pieces) by the REEVCA algorithm a population of pairs of coupled in conglomerates pieces is generated, orderly of according the objective function values. Later on, successive populations of conglomerates are created by means the addition of a new piece using the RLEVCA algorithm until a stop criterion is fulfilled.  For each generated pieces distribution on the foil solution, the cutting sequence optimization task is solved. Decider selects that solution that better satisfies its complete preferences system. 

     The detailed solution to this task and it theoretical foundations will shortly appear published in the specialized literature. 

Searching by Random Exploration of the Extreme of a Function of a  Variable Code

In this case, instead of making evolve a variable code, several codes are simultaneously made evolving. As by the previous algorithm random partitions are made but for each combination of the internal points of the partitions the corresponding solutions by each variable code is decoded and selected the component that belongs together with the combination having the best objective function value. It  is eliminated the subinterval of each variable code that doesn't contain the component of the best solution among the 2n evaluated ones. In each step the current variation interval of any variable code that fulfill the condition that it is equal or less than 2 is totally opened up.  This algorithm wil be called REEVCA algorithm.

     The same as for the previous algortihm, a solutions population is created and upgraded, composed in this case by concrete values of n codes and of the objective function value. The objective function value of the population's worst solution is compared with the corresponding value of each solution generated in the search process and it is substituted, in the case when the recently generated one improves it. 

     In the figure 28 the procedure of generation of codes combinations is illustrated for the particular case of two variable codes. For each generated and decoded solutions combination the objective function is calculated. The generated codes combination is determined to which  the smallest value of this function it is associated and the search subinterval of each variable code is eliminated that doesn't contain the component of the solution with this smaller value. The same as for the previous algorithm, the process stops lapsed a number of successive iterations without improving the solutions quality.   

I hope this answer could help you for solving your problem,

Best wishes,

Dr. José Arzola

nice mr.jose, thank's for your answer... if only i ask for 2D bin packing not 3D Bin Packing, any reference for me to reduce that np-hard ? hard for me to understand your answer, i'm sorry mr.jose... i've studied this problem over 6 month. i read martello and toth book not clear too and not have a statisfied answer... anyway thank's for your share mr.jose... help me anyone...

Shortly: please download " Conciliación óptima de la distribución de piezas de configuración irregular y su corte - Optimal conciliation between distribution on the foil of irregular configuration pieces and it cutting" for reading the explanation of the solution outline. For understanding the method used, there are other works that explain it.

Regards,

José Arzola