Column generation algorithms for mother plate design in steel plants
- PDF / 2,321,755 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 236 Views
Column generation algorithms for mother plate design in steel plants Qi Zhang1 · Shixin Liu1 · Ruiyou Zhang1 · Shujin Qin1 Received: 23 May 2018 / Accepted: 6 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper investigates the mother plate design (MPD) problem which is a typical problem in the production planning of steel plants. The MPD problem refers to a variant of the two-dimensional variable-sized bin packing problem in which the height of a bin is in a given finite set and the width of each bin is continuous in an interval. The problem is first formulated as a mixed integer nonlinear programming model and then linearized into a mixed integer programming model. We present a column generation-based (CG-based) algorithm to approximately solve the MPD problem, in which a height combination scheme is devised to decrease the dimensions of the pricing sub-problem. We present an accelerated CG (ACG) algorithm with improved performance which adopts two heuristic accelerating strategies in the pricing process. We use practical instances collected from a Chinese steel plant to test the performance of the proposed algorithms. The results indicate that the ACG algorithm is suitable for solving real-world instances. Keywords Mother plate design · Two-dimensional variable-sized bin packing problem · Column generation · Accelerated column generation
1 Introduction Plate and strip are the mainstream steel products, accounting for about 45 percent of the total steel products, which are the main raw material of automobile, ship-building and other industries. In modern steel plants, plate and strip products are highly customized according to a make-to-order policy and thus have different sizes and demands. Nevertheless, the mass production mode is adopted for producing mother plates conflicting with individual needs of market. A challenge that steel enterprises have been facing is how to combine the ordered plates of personalized requirements * Ruiyou Zhang [email protected] 1
College of Information Science and Engineering, Northeastern University, Shenyang 110819, Liaoning, China
13
Vol.:(0123456789)
Q. Zhang et al.
OP3
w4 = 2600, l4 = 9000 w3 = 2600, l3 = 8800 W = 5200
OP2 w2 = 2500, l2 = 10400
OP1
OP5
w1 = 2600, l1 = 18800
w5 = 2500, l5 = 9400
Level 1
OP4
Level 2
Fig. 1 Production process of plate and strip products
L = 28200 Fig. 2 Two-staged guillotine cutting mode
into mother plates considering constraints imposed by the production process and machinery, so that the steel enterprises can improve production efficiency and reduce production cost. Fig. 1 shows the production process of plate and strip products, in which molten steel converts into order plates through a sequence of steps. Batches of refined molten steel are poured into continuous casters to produce slabs. Then, the slabs enter the slab yard one by one following the casting sequences and exit according to the rolling sequences. The slabs are reheated in reheating furnaces to
Data Loading...
