An improved lower bound for a general case of the master-plate design problem

This paper investigates a master-plate design problem encountered in the heavy plate mill of the steel industry. The aim of the problem is to pack customer rectangle order-plates into master-plates under consideration of satisfying guillotine cuts, no rotation and no overlap constraints. Unlike the classical two-dimensional bin packing problem, the master-plate design problem we study is a more general case which is not only to determine the size of each order-plate within a specified range but also to decide the size of each created master-plate. The effective design for this problem can help to reduce the trim loss of the master plate, reduce the production cost and improve the material design quality. We formulate this problem as a mixed-integer program, and present an improved lower bound which is based on the split and recompose methods for verifying the effectiveness of a proposed algorithm. Computational experiments show that the improved lower bound is comparable with the one existed in the literature.