Abstract: The billet design problem (BDP) in seamless steel tube production is to assign order tubes to billets under process constraints. Because of the batch rule in practical production, each order has a minimum weight of tubes assigned to any billet. Meanwhile, as the number of tubes assigned to a billet must be an integer, the weight of tubes assigned to any billet is not continuous in its domain. Thus, the BDP discussed herein is more difficult to solve than the slab design and bin packing problems. In this study, a multi-objective mix-integer programming model was built based on a generalized description of the BDP, which is proved to be non-deterministic polynomial (NP) hard. For the case with single billet size wherein two objectives in the model are equivalent, a simplified model was set up and the lower bound of the objective could be found. Further, a two-stage heuristic algorithm based on greedy strategy was proposed to solve the problem. Finally, using computational results, it was proved that the algorithm is effective and efficient in solving the BDP.