Two-staged guillotine cut, two-dimensional bin packing optimisation with flexible bin size for steel mother plate design

Abstract

This paper looks into the steel mother plate design problem. A slab, which is an intermediate work in process, is subsequently rolled into a mother plate with the specific dimensions of thickness, length, and width. The mother plate is then cut into customer order plates. As a slab is rolled into a mother plate through a series of horizontal and vertical rolling processes, different-sized mother plates can be generated from a single-slab type. This flexibility allows for the size of a mother plate to be determined according to the order plates assigned to it. Furthermore, when the order plates are cut from a mother plate, a guillotine cut is required to reduce the production cost. The steel mother plate design problem involves the placing of order plates on the mother plates in a guillotine cut pattern and determining the sizes of the mother plates with the objective of minimising the number of slabs; thus it may be considered as a two-staged guillotine cut, two-dimensional bin packing problem with flexible bin size. This paper introduces the problem, presents several mathematical models, and proposes an iterative two-phase heuristic method consisting of several algorithms to solve the problem. Computational results for the benchmark problems show the effectiveness of the proposed method.

Keywords:

• bin packing problem
• cutting stock problem
• heuristics
• steel mother plate design

Acknowledgements

We would like to express our sincere thanks to Dr. Sanghyuk Park of the Research Institute of Industrial Science & Technology (RIST), Korea, for his help and for providing the benchmark problem sets and related programs. We are also thankful to the three anonymous referees for their invaluable comments and suggestions for improving this paper.