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

摘要： 针对无缝钢管板坯原料库中存在多种圆坯规格的情况,建立了多目标混合整数线性规划模型;通过三划分问题的多项式归结,证明了该问题具有NP难的特性。根据问题的性质,设计了两阶段算法对问题进行求解。第一阶段定义并利用订单自由度将全部订单依次放入圆坯中;第二阶段提出圆坯合并准则对圆坯进行有序合并。通过生产数据和仿真实验证明了算法的有效性和稳定性。

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