关键词: 坯料设计, 无缝钢管, 启发式算法, 装箱问题

Abstract: For the case with multiple billet sizes,a mixed integer programming model was established,which was proved to be an NP hard problem by concluding from three partition problem.According to greedy strategy,a two-stage algorithm was proposed to solve the problem.In the first stage,the degree of assignment was defined to evaluate the difficulty of assigning tubes of an order to a billet,and all the orders sorted by degree of assignment were assigned to the billets.In the second stage,a merging principle was proposed to decrease the number of billets.Through practical and simulation experiments,the proposed algorithm was proved to be effective and efficient.

Key words: billet design, seamless steel tube, heuristic algorithm, bin packing problem