Research On Hybrid Algorithm For The 2D Variable Size Bin Packing Problem With Partial Rotatable And Guillotine Cut Constraint

Cutting and packing problem is a process that a given material must be cut into a smaller set of parts with given shapes and numbers according to a certain technology.The problem is considered as a non-deterministic polynomial-time(NP)-hard problem,and the calculation complexity has the trend of exponential increase with parts size increased.Cutting and packing problem is widely used in many areas in manufacturing industries,and the study on it has important economic value and significance.This paper mainly deals with the 2D Variable Size Bin Packing problem with partial Rotatable parts and Guillotine cut constraint.On the basic summarizing of the background and significance of the problem,the paper provides an overview of the bin packing problem literature.Considered the specific characteristics and the constraints in the problem of 2DVSBP|*|G,the paper presents a mathematical model,and sums up the related theory of the problem of rectangular packing.On the basis of analyzing and comparing the advantages and disadvantages of common heuristic algorithms and intelligent optimization algorithms,the scoring strategy is integrated into the heuristic algorithm,and optimized the results by the simulated annealing algorithm;the algorithm can get higher fitness value.And then introduces the basic theory of Genetic algorithm,designs the algorithm based on the features of the problem,including the encoding strategy,population structuring,fitness function,selection,crossover and mutation operator,decoding.Then by melting the simulated annealing algorithm into genetic algorithm,proposed the hybrid GASA algorithm.The hybrid algorithm can solve the problems of local optimization and improve the efficiency of the algorithm by melting the advantages of the two algorithms.According to the author's work experience,requirement analysis and modeling are carried out for optimal layout system using object-oriented method;and designed a system of database,data input,automatic and interactive optimization,and output module.Finally,the paper draws some conclusions and prospects.