Variable neighborhood search for integrated determination of charge batching and casting start time in steel plants

Abstract

The integrated determination of the charge batching and casting start time (CBCST) is a combinatorial optimization problem extracted from the production and operations management of steel plants. A hierarchical optimization method based on variable neighborhood search (VNS) is proposed in this paper for integrated determination of CBCST. The number of casts on each continuous caster and the number of charges in each cast are determined in the encoding. The decoding process is decomposed into solving two sub-problems. A mixed integer programming (MIP) model is built for the first sub-problem by considering it as a prize collecting multiple traveling salesmen problem, and a VNS algorithm is proposed for solving the model. In addition, another MIP model is developed for the second sub-problem, and the model is solved by CPLEX directly. Experimental results on practical production data demonstrate that the proposed algorithm is effective for determining the charge batching and the casting start time simultaneously.

Keywords

Variable neighborhood search charge batching casting start time determining mixed integer programming

1 Introduction

In a steel plant, continuous caster is the only continuous working machine to solidify the molten steel into slabs. A ladle load of hot metal or molten steel is called a charge, which is the basic unit of the production and operations management of steel plants. The set of charges continuously processed without interruption on the same continuous caster is called a cast. Affected by the specific production characteristics of continuous casting, production costs may be incurred for processing two adjacent charges in the same cast. For example, the two charges associated with different steel grades will lead to hybrid-grade slabs. Therefore, the optimal decision of charge batching (charge selection and charge sequencing) is always a hot topic in the research field of production and operations management [1].

Chang et al. [2] formulated the charge batching problem as an integer programming model, and proposed an efficient heuristic algorithm to solve the model by employing the column generation approach combined with a simple round-off scheme. Tang et al. [3, 4] developed two algorithms, a tabu search-based heuristic and an iterated local search algorithm, for solving the charge batching problem. Later, an integrated charge batching and casting width selection problem was studied by Tang et al. [5], and a branch-and-price solution approach is developed to obtain optimal solutions. Xue et al. [6] employed a pseudo traveling salesman problem to describe the charge batching problem, and proposed a modified discrete particle swarm optimization to solve it.

Most of the existing studies regard the lifespan of a tundish (about 300 to 400 minutes), which is a buffer between the ladle and the continuous caster for continuous casting production, as the maximum capacity of continuous casting production. However, with the development of tundish quick-change technique, continuous casting production between tundishes can also be realized in modern steel plants. Considering that the characteristic will improve the flexibility of decision making of charge batching, Ma et al. [7] studied the new charge batching problem by considering the lifespan of a mold, another component of a continuous caster, as the maximum capacity of continuous casting production. However, due to a mold always has a long lifespan (more than 20 days), the continuous casting production cannot be maintained until a mold reaches its lifespan in the practical production process. Therefore, one of the biggest difficulties of the new charge batching problem is how to reasonably determine the number of charges in each cast. The number of charges in each cast will affect the production rhythm of continuous casters. In addition, the casting start time of each cast will also affect the production rhythm of continuous casters. Therefore, charge batching and casting start time should be optimized simultaneously.

This paper studies on the modeling methods and solving algorithms for the integrated determination of the charge batching and casting start time (CBCST) in steel plants. The determination of CBCST is a new optimization problem extracted from the production and operations management of steel plants. In addition, it is NP-hard and large-scale in practical applications. Although such peer methods as fuzzy method [8], deep learning method [9] and particle swarm optimization [10] have been applied as intelligent algorithms, variable neighborhood search (VNS) [11] is a simple yet effective approach used for intelligent optimization with NP-hard natures [12 –15]. In this paper, through analyzing the characteristics of CBCST problem, a hierarchical optimization method based on VNS is proposed for problem solving.

The rest of the paper is organized as follows. The characteristics of CBCST problem are described in Section 2. In Section 3, the details of the solution method are introduced. In addition, experimental results are reported in Section 4. Finally, Section 5 will conclude this study.

2 Problem statement

As shown in Fig. 1, the steel manufacturing process mainly contains three phases: ironmaking, steelmaking (steel plant) and steel-rolling. The raw material for steelmaking is the hot metal produced by blast furnace in the ironmaking phase, and the slab produced by continuous caster in the steelmaking phase is the raw material for the following steel rolling. In the daily production and operations management process of steel plants, before making a production schedule [16, 17], CBCST should be integrated solved to determine the number of casts to be processed on each continuous caster, the charge selection and charge sequencing of each cast, and the casting start time of each cast.

Fig.1

The steel manufacturing process.

The technological features of CBCST are described as follows: 1) since charges in a cast need to be continuously processed in a continuous caster, the molten steel of two adjacent charges will be mixed. Each charge is associated with a steel grade. According to the processing requirements, the steel grades of two adjacent charges in a cast must be compatible (the metallurgical compositions of the two grades are the same or close). For two adjacent charges with compatible steel grades, if their steel grades are the same, no production cost will be incurred. Otherwise, production cost will be incurred because hybrid-grade slabs will be produced; 2) when charges with different thicknesses need to be processed, a continuous caster must be stopped for several hours to adjust the thickness of the nozzle located at the bottom of a mold. In order to avoid frequent adjustments, steel plants generally produce charges of the same thickness for several days. Due to the planning period of CBCST is generally not more than a day, all charges are assumed to have the same thickness in this paper; 3) since the width of the nozzle is adjustable in the process of continuous casting, charges with different widths are allowed in a cast. However, in order to avoid possible risks, the nozzle width can only be adjusted from wide to narrow (adjusting from narrow to wide may cause unplanned casting break). In addition, there exists a maximum allowable value for casting width jump between two adjacent charges (exceeding the maximum allowable value may cause molten steel spillover). Although different widths are allowed in a cast, casting width jump will also bring production cost because irregular slabs will be produced; 4) continuous casting production is very important to energy consumption reduction and higher productivity in steel plants. Therefore, caster interruption among the charges in a cast is prohibited; 5) a setup time is required for processing a new cast on a continuous caster; 6) the number of charges included in a cast should be within a reasonable range. Namely, it cannot be less than a minimum allowable value, and also cannot be greater than a maximum allowable value; and 7) the production rhythm of continuous casters must match the supply rhythm of hot metal. The hot metal produced by blast furnace is contained in ladles for transportation. Therefore, for steelmaking production, the supply rhythm of hot metal refers to the arrival time rhythm of hot metal ladles in steel plants.

The optimization objectives for CBCST are accordingly described as follows: 1) since production cost will be incurred by steel grade jump and casting width jump in a cast, minimizing the production costs in all the casts is an optimization objective of CBCST; 2) since production cost will be incurred for processing a new cast, the number of casts should be minimized; and 3) in order to reduce the costs for inventory/delay to the steel rolling phase, each charge should be completed on a continuous caster at the rolling due date predetermined at planning level. In other words, the earliness/tardiness of steel rolling due date should be minimized.

3 Modeling and optimization algorithm for CBCST

3.1 The overall framework of the solution method

In the existing studies, charge batching problem is always treated as a special traveling salesman problem (TSP) [1]. Since TSP is NP-hard, charge batching problem is also NP-hard. Therefore, the integrated determination of CBCST must be NP-hard. For a large-scale combinatorial optimization problem with NP-hard natures, the quality of final solution and computational time are two equally important criteria to evaluate a solution method. Therefore, in this paper, a hierarchical optimization method based on VNS is proposed to determine CBCST.

VNS is a simple yet effective metaheuristic whose basic idea is systematic change of neighborhood structures within the local search algorithm. The procedure of VNS is described in Fig. 2. One may refer to [11] for a complete introduction. Encoding design is the basic step for applying VNS algorithm. As described before, there are many decision variables in our problem. Although a multi-pattern deep fusion model has been used to combine different variables into an integrated fashion [18], too many information will affect the performance of the algorithm. Therefore, in this paper, only the number of casts on each continuous caster and the number of charges in each cast are included in the encoding. As shown in Fig. 3, a real number in the encoding represents a cast. More specifically, the integer part of the real number represents the index of the continuous caster allocated to process this cast, and the fractional part of the real number represents the number of charges included in this cast. Recall that the number of charges included in a cast should be within a reasonable range. Therefore, the feasibility of encoding must be guaranteed in the process of initialization and neighborhood search.

Fig.2

The procedure of VNS.

Fig.3

The encoding and hierarchical decoding process.

To decode a complete solution, a hierarchical modeling and optimization strategy is proposed. As shown in Fig. 3, charge selection and sequencing of all the casts are first determined, and then the casting start time of all the casts are determined. The details of their mathematical models and solution methods are described in the following Sections 3.2 and 3.3, respectively.

Neighborhood structure design is the key to the application of VNS algorithm. According to the characteristics of CBCST problem and the proposed encoding method, five neighborhood structures (N₁, N₂, N₃, N₄, N₅) are designed in this paper. As shown in Fig. 4, N₁ represents that a neighbor of a solution is obtained by updating the number of charges of two casts allocated in the same continuous caster. N₂ represents that a neighbor of a solution is obtained by transferring a cast from one continuous caster to another. N₃ represents that a neighbor of a solution is obtained by splitting one cast into two casts. N₄ represents that a neighbor of a solution is obtained by combining two casts allocated in the same continuous caster into one cast. N₅ represents that a neighbor of a solution is obtained by exchanging the two casts that are allocated to different continuous casters. The large neighborhood structures, i.e., N₁, N₂ and N₃, are used in the shaking phase to jump out of local optimum. The small neighborhood structures, i.e., N₄ and N₅, are used in the local search phase to obtain the local optimum. Note that the total number of charges cannot be changed in the neighborhood search process.

Fig.4

The neighborhood structures for solving CBCST problem.

3.2 Modeling and solving for charge selection and sequencing

As described in Section 2, there are three optimization objectives in CBCST problem. There is no doubt that the objective 1) should be considered in this sub-problem. Since the number of casts is determined in the encoding, the objective 2) does not need to be considered here. As for the objective 3), although the casting start times of casts are not determined in this sub-problem, we should avoid arranging charges with huge different rolling due dates to a cast because charges in a cast should be continuously processed. In addition, we should try to arrange charges with earlier rolling due dates to casts.

Based on the above analysis, the charge selection and sequencing problem can be interpreted as a prize collecting multiple traveling salesmen problem (see Fig. 3). Suppose that there are J (determined by encoding) salesmen, each salesman (cast) starts and ends at a source city (dummy charge 0) through visiting a certain number (determined by encoding) of cities. Each city (charge) can be visited at most once. If a city is visited, a prize (related to the rolling due date) is obtained. The objectives are to determine J routes so as to minimize the total distance traveled (penalties caused by jumping between adjacent charges) and maximize the collected prizes (equivalent to minimize the total rolling due date). The notations used for the mathematical model are described as follows.

Parameters

i: charge index, i ∈ {0, 1, 2, …, I}, I is the total number of charges, charge 0 is the dummy charge;

Ψ: set of indices of all charges, i ∈ Ψ;

j: cast index, j ∈ {1, 2, …, J};

n_j: the number of charges in cast j, $\sum_{j = 1}^{J} n_{j}$ is the total number of charges planned to produce;

g_i: steel grade index of charge i;

w_i: casting width of charge i;

d_i: rolling due date of charge i;

cg_ii′: penalty caused by jumping between charge i and i′ with different steel grades,

${cg}_{{ii}^{'}} = {\begin{matrix} α_{{ii}^{'}} (| g_{i} - g_{i^{'}} |) & if g_{i} is compatible with g_{i^{'}} \\ \infty & otherwise \end{matrix}$ (1) where α_ii′ is the penalty coefficient for steel grade jump;

cw_ii′: penalty caused by jumping between charge i and i′ with different casting widths,

${cw}_{{ii}^{'}} = {\begin{matrix} β_{{ii}^{'}} (w_{i} - w_{i^{'}}) & if 0 \leq w_{i} - w_{i^{'}} \leq W \\ \infty & otherwise \end{matrix}$ (2) where β_ii′ is the penalty coefficient for casting width jump, W is the maximum allowable value for casting width jump;

cd_ii′: penalty caused by jumping between charge i and i′ with different rolling due dates,

${cd}_{{ii}^{'}} = {\begin{matrix} γ_{{ii}^{'}} (d_{i^{'}} - d_{i}) & if d_{i} - d_{i^{'}} \leq 0 \\ 2 γ_{{ii}^{'}} (d_{i} - d_{i^{'}}) & otherwise \end{matrix}$ (3) where γ_ii′ is the penalty coefficient for rolling due date jump;

c_ii′: the total penalty caused by jumping between charge i and i′, c_ii′ = cg_ii′ + cw_ii′ + cd_ii′;

λ₁, λ₂: objective weight coefficient.

Decision variables

x_ii′j: 0/1 variable that is equal to one if and only if charge i is processed immediately before charge i′ in cast j;

y_ij: 0/1 variable that is equal to one if and only if charge i is allocated to cast j;

u_ij: processing sequence of charge i in cast j.

Mathematical model

$\begin{matrix} Min {OB}_{1} & = & λ_{1} \sum_{i = 0}^{I} \sum_{i^{'} = 0}^{I} c_{{ii}^{'}} \sum_{j = 1}^{J} x_{{ii}^{'} j} \\ + λ_{2} \sum_{i = 1}^{I} d_{i} \sum_{j = 1}^{J} y_{ij} \end{matrix}$ (4) subject to $\begin{matrix} \sum_{i = 0}^{I} x_{{ii}^{'} j} = y_{i^{'} j}, \forall i^{'} \in {0, 1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J} \end{matrix}$ (5) $\begin{matrix} \sum_{i^{'} = 0}^{I} x_{{ii}^{'} j} = y_{ij}, \forall i \in {0, 1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J} \end{matrix}$ (6) $\begin{matrix} u_{ij} - u_{i^{'} j} + n_{j} x_{{ii}^{'} j} \leq n_{j} - 1, \forall i \in {1, 2, \dots, I}, \\ \forall i^{'} \in {1, 2, \dots, I}, i \neq i^{'}, \forall j \in {1, 2, \dots, J} \end{matrix}$ (7) $\begin{matrix} 1 \leq u_{ij} \leq n_{j}, \forall i \in {1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J} \end{matrix}$ (8) $y_{0 j} = 1, \forall j \in {1, 2, \dots, J}$ (9) $\sum_{j = 1}^{J} y_{ij} \leq 1, \forall i \in {1, 2, \dots, I}$ (10) $\sum_{i = 1}^{I} y_{ij} = n_{j}, \forall j \in {1, 2, \dots, J}$ (11) $\begin{matrix} x_{{ii}^{'} j} \in {0, 1}, \forall i \in {0, 1, 2, \dots, I}, \\ \forall i^{'} \in {0, 1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J}, i \neq i^{'} \end{matrix}$ (12) $\begin{matrix} y_{ij} \in {0, 1}, \forall i \in {0, 1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J} \end{matrix}$ (13) $\begin{matrix} u_{ij} \in N, \forall i \in {0, 1, 2, \dots, I}, \\ \forall j \in {1, 2, \dots, J} \end{matrix}$ (14)

Objective (4) is to minimize the total penalties caused by jumping between adjacent charges and the total rolling due date. Constraints (5–8) specify the sequence of a cast (TSP for each cast). Constraints (9–10) ensure that the dummy charge 0 must be allocated in each cast, while other charges are allocated at most once. Constraint (11) guarantees that the number of charges in each cast must be equal to the predetermined value. Constraints (12–14) limit the value range of decision variables.

Since the above model is a mixed integer programming (MIP) model, it can be solved by a general-purpose MIP solver (e.g. GUROBI or CPLEX) directly. However, experimental results show that using this method will take a long time to solve the daily problem scale in steel plants. Since charge selection and sequencing problem is just a sub-problem of CBCST, too long solution time will affect the efficiency of the whole algorithm. Therefore, an effective algorithm with the ability of obtaining a high-quality solution within acceptable computational times should be designed.

There are several studies on designing the optimization algorithms for multiple traveling salesmen problem (MTSP) [19]. However, as far as we know, few studies focused on the multiple traveling salesmen problem with prize collecting, determined number of traveling salesmen and determined number of visiting cities of each traveling salesman. In this paper, a VNS algorithm is proposed to solve the above MIP model on the basis of the VNS algorithm proposed by Soylu [20]. Due to the special characteristics of the present problem, the initialization method and neighborhood structures described in [20] need to be modified.

For the initialization, our initialization method is a greedy construction heuristic, which selects charges and determines their processing sequence to each cast in turn by using the idea of savings proposed by Clark and Wright [21]. For ease of description, some new notations should be defined: Ω represents the set of indices of all casts, Ω = {1, 2, …, J}; Ψ′ represents the set of indices of all charges except the dummy charge, Ψ′ = {1, 2, …, I}; Ψ_j represents the set of indices of all charges in cast j; fi (j) represents the first charge in cast j; li (j) represents the last charge in cast j; bi (j, i) represents the immediate predecessor charge of charge i in cast j; S (i, i′) represents the objective increment when charge i and charge i′ are added to cast j simultaneously as two adjacent charges, S (i, i′) = λ₁c_i,i′ + λ₂ (d_i + d_i′); Sf (i) represents the objective increment when charge i is added to cast j as its new first charge, Sf (i) = λ₁c_i,fi(j) + λ₂d_i; Sl (i) represents the objective increment when charge i is added to cast j as its new last charge, Sl (i) = λ₁c_li(j),i + λ₂d_i; Si (i, i′) represents the objective increment when charge i is added to cast j as the new immediate predecessor charge of charge i′ (i′ ≠ fi (j)), Si (i, i′) = λ₁ (c_bi(j,i′),i + c_i,i′ - c_{bi(j,i′),i′}) + λ₂d_i. The details of the heuristic algorithm for constructing initial solution are given as follows.

Step 1. initialize set Ω with J casts, and initialize set Ψ′ with I charges;

Step 2. if Ω≠ ∅, set Ψ_j =∅ (j is the first cast of Ω), go to Step 3, otherwise, end the algorithm;

Step 3. calculate the S (i, i′) between any two charges in Ψ′, add the two charges with minimum S (i, i′) to Ψ_j, and then delete these two charges from Ψ′. Initialize a counter count = 2;

Step 4. if count < n_j, go to Step 5, otherwise, go to Step 6;

Step 5. calculate the Sf (i), Sl (i), and all the Si (i, i′) (i′ ∈ Ψ_j) of each charge i in Ψ′. The objective increment of charge i is the minimum value among Sf (i), Sl (i), and all the Si (i, i′). Add the charge with minimum objective increment to the corresponding location of Ψ_j, and then delete the charge from Ψ′. Set count = count + 1, go to Step 4;

Step 6. Save set Ψ_j, delete the first cast of Ω, go to Step 2.

For neighborhood structures, six neighborhood structures (one-point move, two-point move, or-opt2 move, or-opt3 move, three-point move, 2-opt) are used in the VNS algorithm proposed by Soylu [20]. However, since the number of visiting cities of each traveling salesman is determined in our problem, only the two neighborhood structures (two-point move and 2-opt) can be used here. In addition, since prize collecting is considered in our problem, another neighborhood structure named swap is also employed. Swap represents that a neighbor of a solution is obtained by using an unselected charge to replace a selected charge. The diagrammatic sketch of the three neighborhood structures is shown in Fig. 5.

Fig.5

The neighborhood structures for solving charge selection and sequencing problem.

3.3 Modeling and solving for casting start time

As shown in Fig. 3, after the charge selection and sequencing of all the casts are determined, the casting start time of all the casts need to be determined to decode a complete solution. For modeling the casting start time determining problem, the following notations should be described first.

Parameters

i: charge index, $i \in {1, 2, \dots, \tilde{I}}$ , $\tilde{I}$ is the total number of charges in all the casts ( $\tilde{I} \leq I$ ). The indices of charges need to be consecutively numbered according to the determined casting order in casts, which is the results obtained by solving charge selection and sequencing problem;

$\tilde{Ψ}$ : set of indices of all charges, $i \in \tilde{Ψ}$ ;

j: cast index, j ∈ {1, 2, …, J};

${\tilde{Ψ}}_{j}$ : set of indices of all charges in cast j. For any j1 ≠ j2, ${\tilde{Ψ}}_{j 1} \cap {\tilde{Ψ}}_{j 2} = \emptyset$ . $\sum_{j = 1}^{J} | {\tilde{Ψ}}_{j} | = \tilde{I}$ ;

m: continuous caster index, m ∈ {1, 2, …, M};

Ω_m: set of indices of all casts allocated on the continuous caster m, the number of casts in Ω_m is |Ω_m|, $\sum_{m = 1}^{M} | Ω_{m} | = J$ ;

fi (j): the first charge in cast j;

li (j): the last charge in cast j;

ct_i: average processing time of charge i on its allocated continuous caster;

ft_i: average flow time of charge i in the steel plant, note that the processing time of charge i on the continuous caster is not included in ft_i;

d_i: rolling due date of charge i;

st: setup time between two adjacent casts on the same continuous caster;

et_m: earliest available time of continuous caster m;

r: time index of hot metal ladle released for the steel plant, r ∈ {1, 2, …, R}, $R = \tilde{I}$ ;

ht_r: time value corresponding to r, ht_r-1 ≤ ht_r;

λ₃: objective weight coefficient;

U: a sufficient large positive integer.

Decision variables

s_i: casting start time of charge i;

g_i,r: 0/1 variable that is equal to one if and only if casting start time s_i is greater than or equal to the sum of ht_r and ft_i;

h_j,j′: 0/1 variable that is equal to one if and only if the casting start time of cast j is less than the casting start time of cast j′.

Mathematical model

$\begin{matrix} Min {OB}_{2} & = & λ_{3} \sum_{i \in \tilde{Ψ}} (max {0, s_{i} + {ct}_{i} - d_{i}} \\ - min {0, s_{i} + {ct}_{i} - d_{i}}) \end{matrix}$ (15) subject to $\begin{matrix} s_{i} \geq {et}_{m}, \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \forall i \in {\tilde{Ψ}}_{j} \end{matrix}$ (16) $\begin{matrix} s_{li (j)} + {ct}_{li (j)} + st \leq s_{fi (j^{'})} + (1 - h_{j, j^{'}}) U, \\ \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, \\ j \neq j^{'} \end{matrix}$ (17) $\begin{matrix} s_{li (j^{'})} + {ct}_{li (j^{'})} + st \leq s_{fi (j)} + h_{j, j^{'}} U, \\ \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, \\ j \neq j^{'} \end{matrix}$ (18) $\begin{matrix} h_{j, j^{'}} + h_{j^{'}, j} = 1, \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \\ \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (19) $\begin{matrix} s_{i} + {ct}_{i} = s_{i + 1}, \forall j \in {1, 2, \dots, J}, \forall i, i + 1 \in {\tilde{Ψ}}_{j} \end{matrix}$ (20) $\sum_{i \in \tilde{Ψ}} g_{i, r} \geq R - r + 1, \forall r = {1, 2, \dots, R}$ (21) $\begin{matrix} s_{i} + (1 - g_{i, r}) U \geq {ht}_{r} + {ft}_{i}, \forall i \in \tilde{Ψ}, \\ \forall r = {1, 2, \dots, R} \end{matrix}$ (22) $\begin{matrix} s_{i} - g_{i, r} U < {ht}_{r} + {ft}_{i}, \forall i \in \tilde{Ψ}, \\ \forall r = {1, 2, \dots, R} \end{matrix}$ (23) $s_{i} \geq 0, \forall i \in \tilde{Ψ}$ (24) $g_{i, r} \in {0, 1}, \forall i \in \tilde{Ψ}, \forall r = {1, 2, \dots, R}$ (25) $\begin{matrix} h_{j, j^{'}} \in {0, 1}, \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \\ \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (26)

Objective (15) is to minimize the earliness/tardiness of steel rolling due date. Constraint (16) ensures that charges must not be processed on its allocated continuous caster before its earliest available time. Constraints (17–18) guarantee that there must be a setup time between any two consecutive casts on a continuous caster. Constraint (19) ensures that there must be a precedence relationship on a continuous caster for processing any two casts. Constraint (20) ensures that any two consecutive charges in a cast must be processed continuously without any interruption. Constraint (21) ensures that the production rhythm of continuous casters must match the supply rhythm of hot metal ladles. Constraints (22–23) describe the relationship between the decision variables s_i and g_i,r. Constraints (24–26) limit the value range of decision variables.

One can find that objective (15) is nonlinear. For ease of solving, we set Y_i = max {0, s_i + ct_i - d_i} and Z_i = - min {0, s_i + ct_i - d_i}. Obviously, Y_i and Z_i are nonnegative. We also have the following relations: s_i = Y_i - Z_i - ct_i + d_i. Therefore, substituting all the s_i in the constraints and reformulating the objective by using Y_i and Z_i, the original nonlinear model can be converted into a MIP model.

In this paper, we choose to use CPLEX to solve the MIP model directly. For solving the daily problem scale, the solution time of CPLEX is about 10 seconds. Since the main algorithm in CPLEX to solve the MIP model is branch and cut, designing some valid inequalities (cuts) based on the problem characteristics and adding them to the model will improve the solving efficiency. According to the fact that the casting sequence of charges in a cast has been already determined by solving the charge selection and sequencing problem, 6 valid inequalities are designed as follows. Their graphical interpretation is shown in Fig. 6. Experimental results show that the solving efficiency is doubled by adding these 6 valid inequalities to the model (the solution time can be reduced to 4 seconds for solving the daily problem scale). $\begin{matrix} \sum_{i = i + 1}^{li (j)} g_{i, r} \geq (li (j) - i) + (g_{i, r} - 1) U, \\ \forall j \in {1, 2, \dots, J}, \\ \forall i \in {fi (j), \dots, li (j) - 1}, \forall r = {1, 2, \dots, R} \end{matrix}$ (27) $\begin{matrix} \sum_{i = fi (j)}^{i - 1} g_{i, r} \leq g_{i, r} U, \forall j \in {1, 2, \dots, J}, \\ \forall i \in {fi (j) + 1, \dots, li (j)}, \forall r = {1, 2, \dots, R} \end{matrix}$ (28) $\begin{matrix} g_{li (j), r} \leq g_{fi (j^{'}), r} - h_{j, j^{'}} + 1, \forall r = {1, 2, \dots, R}, \\ \forall m \in {1, 2, \dots, M}, \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (29) $\begin{matrix} g_{fi (j^{'}), r} \geq g_{li (j), r} + h_{j, j^{'}} - 1, \forall r = {1, 2, \dots, R}, \\ \forall m \in {1, 2, \dots, M}, \\ \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (30) $\begin{matrix} g_{li (j^{'}), r} \leq g_{fi (j), r} + h_{j, j^{'}}, \forall r = {1, 2, \dots, R}, \\ \forall m \in {1, 2, \dots, M}, \\ \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (31) $\begin{matrix} g_{fi (j), r} \geq g_{li (j^{'}), r} - h_{j, j^{'}}, \forall r = {1, 2, \dots, R}, \\ \forall m \in {1, 2, \dots, M}, \\ \forall j \in Ω_{m}, \forall j^{'} \in Ω_{m}, j \neq j^{'} \end{matrix}$ (32)

Fig.6

The graphical interpretation of the 6 valid inequalities.

4 Experimental results

4.1 Parameter tuning

The performance of different parameters of the proposed algorithm for solving daily CBCST problems is first analyzed. Two parameters are calibrated here: t_mvns (the maximum allowable CPU time of VNS for solving CBCST problem) and t_tvns (the maximum allowable CPU time of VNS for solving charge selection and sequencing problem, which is a sub-problem of CBCST). We obtained 12 parameter combinations by carrying out a full factorial experimental testing the two parameters at the following levels:

t_mvns: 4 levels (200 seconds, 400 seconds, 600 seconds and 800 seconds);

t_tvns: 3 levels (2 seconds, 5 seconds and 8 seconds).

Since there are no benchmarks designed for CBCST problem, we generated some problem instances based on the real-world data extracted from the steel plant of Panzhihua Iron and Steel Corporation in China. There are 5 continuous casters (CC for short) in the steel plant. The problem structures are described as follows: the total number of charges I varies among 3 levels (80, 100, 120); the total number of charges planned to produce $\tilde{I}$ varies among 3 levels (50, 60, 70). We generated one instance for each combination. Thus, 9 instances were generated in total. Other production data for the instances were generated by a uniform distribution in the following range: steel grade g_i ∈ [1, 10], casting width w_i ∈ {1100, 1150, 1200, 1250, 1300, 1350}, rolling due date d_i ∈ [250, 1350], average processing time of charge i on CC1 ${ct}_{i}^{1} \in [40, 44]$ , average processing time of charge i on CC2 ${ct}_{i}^{2} \in [60, 64]$ , average processing time of charge i on CC3 ${ct}_{i}^{3} \in [46, 51]$ , average processing time of charge i on CC4 ${ct}_{i}^{4} \in [53, 57]$ , average processing time of charge i on CC5 ${ct}_{i}^{5} \in [60, 64]$ , average flow time in the steel plant ft_i ∈ [204, 221, 214, 211, 243, 250, 242], release time of hot metal ladle ht_r ∈ [0, 1100]. The earliest available time of all the continuous casters (from CC1 to CC5) are 212, 193, 211, 206 and 213, respectively. The setup time between two adjacent casts st = 30. The penalty coefficients are set as follows: α_ii′ = 1, β_ii′ = 0.01, γ_ii′ = 0.3, $λ_{1} = 1 / \sum_{j = 1}^{J} n_{j}$ , $λ_{2} = 0.05 / \sum_{j = 1}^{J} n_{j}$ , $λ_{3} = 0.2 / \tilde{I}$ , and the penalty coefficient for processing a cast is set to 15.

Each parameter combination will result in one candidate configuration of the proposed algorithm. Hence, 12 different configurations are obtained. We used C++ to implement all the configurations (the MIP model for determining casting start time was solved by CPLEX 12.5.1), and ran the 9 instances independently 3 times on a PC with 2.6 GHz CPU and 4 G RAM under the windows 7 operating system (64-bit) for each configuration. The relative percentage increase (RPI) is calculated as the metric for comparison. RPI is calculated by RPI (F) = (F - F *)/F * ×100, where F is the solution that is produced by a given configuration, and F* is the best solution that is obtained by all of the configurations.

The box plots of the RPI values given by each configuration through solving the instances are shown in Fig. 7. From the results we can find that the performance of the configurations with t_mvns = 400 is much better than that of the configurations with t_mvns = 200. Although the performance of the configurations with t_mvns = 600 or 800 is better than that of the configurations with t_mvns = 400, the performance has not improved a lot by spending more solution times. In addition, we also can find that the performance of the configurations with t_tvns = 5 performs best than the others. The reason is that a small t_tvns will result a poor solution of charge selection and sequencing problem. However, a big t_tvns will affect the overall computational efficiency because the charge selection and sequencing problem is only a sub-problem of CBCST. Therefore, by synthetically considering the quality of solution and computational efficiency, the best combination for solving daily CBCST problems is recommended as t_mvns = 400 and t_tvns = 5.

Fig.7

The box plots of the RPI values.

4.2 Performance analysis of VNS for solving charge selection and sequencing problem

In the decoding process of the proposed algorithm, the optimal solution of casting start time determining problem can be obtained efficiently by CPLEX. However, for charge selection and sequencing problem (the other sub-problem), a VNS algorithm is designed to obtain a high-quality solution within acceptable computational times. Therefore, in this section, we are going to analyze the performance of the VNS algorithm. More specifically, the VNS algorithm is compared with CPLEX (the model of charge selection and sequencing problem is a MIP model, and it can be solved by CPLEX) to observe the gap between the solution obtained by the VNS and the optimal solution obtained by CPLEX.

Since it will take a long time for CPLEX to solve the daily problem scale, we designed 9 new small scale instances as follows: the total number of charges I varies among 3 levels (60, 80, 100); and the total number of charges planned to produce $\tilde{I}$ varies among 3 levels (10, 20, 30). The steel grade, casting width and rolling due date of each charge were generated by using the same method described in Section 4.1. Moreover, the instances used for charge selection and sequencing problem should determine the number of casts J and the number of charges in each cast n_j. To reduce the complexity of instances, J = 1 and n_j = 10 (j = 1) are set for the instances with $\tilde{I} = 10$ ; J = 2, n_j = 8 (j = 1) and n_j = 12 (j = 2) are set for the instances with $\tilde{I} = 20$ ; J = 3, n_j = 7 (j = 1), n_j = 9 (j = 2) and n_j = 14 (j = 3) are set for the instances with $\tilde{I} = 30$ .

The objective values OB₁ obtained by CPLEX and our VNS algorithm are shown in Table 1. From Table 1 we can find that the small scale instances ( $\tilde{I} = 10$ or 20) are solved efficiently by CPLEX. However, for those instances with $\tilde{I} = 30$ , about 100 seconds need to be cost to obtain the optimal solutions by CPLEX. With respect to the results of VNS algorithm, we can find that the objective values obtained by the VNS are very close to the optimal objective values obtained by CPLEX. The metric gap = (VNS _ OB₁ - CPLEX _ OB₁)/CPLEX _ OB₁ is defined to describe quantitatively. Then, the average gap is 0.117 when t_tvns = 2, the average gap is 0.055 when t_tvns = 5, and the average gap is 0.036 when t_tvns = 8. Therefore, although the VNS algorithm cannot guarantee to obtain the optimal solution, it can obtain a high-quality solution in a short time. This performance is more helpful to solve large scale problems.

Table 1
Computational results of CPLEX and the VNS algorithm for solving charge selection and sequencing problem

Instance ( $I * \tilde{I}$ ) CPLEX VNS

OB ₁ Solution time (s) OB₁ (t_tvns = 2s) OB₁ (t_tvns = 5s) OB₁ (t_tvns = 8s)

6010 50.84 3 57.17 51.86 51.26

6020 35.34 7 39.51 38.04 36.57

6030 45.32 105 49.64 47.25 47.25

8010 34.68 3 37.06 34.68 34.68

8020 31.39 14 35.17 33.98 32.75

8030 41.39 115 48.72 44.32 43.75

10010 28.95 4 31.24 29.89 29.57

10020 31.80 19 35.53 34.67 33.54

100*30 39.98 98 45.91 43.14 42.54

Instance ( $I * \tilde{I}$ )	CPLEX	VNS
60*10	50.84	3	57.17	51.86	51.26
60*20	35.34	7	39.51	38.04	36.57
60*30	45.32	105	49.64	47.25	47.25
80*10	34.68	3	37.06	34.68	34.68
80*20	31.39	14	35.17	33.98	32.75
80*30	41.39	115	48.72	44.32	43.75
100*10	28.95	4	31.24	29.89	29.57
100*20	31.80	19	35.53	34.67	33.54
100*30	39.98	98	45.91	43.14	42.54

4.3 Comparisons between the proposed method and manual decision method

This section describes an experiment that was conducted with five day of real data for CBCST problem, and makes comparisons with the manual decision method that was applied in the steel plant of Panzhihua Iron and Steel Corporation in China.

The computational results for different instances are presented in Table 2. For each instance, the values of different objective functions including penalties for charge selection and sequencing (OB₁), penalties for casting start time determining (OB₂), penalties for the number of casts (OB₃), and the sum of penalties are presented. Note that the value of OB₁ is calculated according to formula (4), the value of OB₂ is calculated according to formula (15), and the value of OB₃ is the product of the penalty coefficient for processing a cast (see Section 4.1) and the number of casts in the final solution.

Table 2
Computational results of the manual decision method and the proposed algorithm for solving CBCST problem

ID Manual decision Proposed algorithm

OB ₁ OB ₂ OB ₃ Sum OB ₁ OB ₂ OB ₃ Sum

1 79.43 35.24 120 234.67 73.24 34.56 120 227.8

2 73.28 38.74 90 202.02 66.45 39.53 90 195.98

3 71.25 34.79 120 226.04 70.23 36.28 105 211.51

4 77.42 39.67 135 252.09 72.52 37.16 135 244.68

5 70.89 37.13 90 198.02 67.14 38.92 75 181.06

ID	Manual decision	Proposed algorithm
1	79.43	35.24	120	234.67	73.24	34.56	120	227.8
2	73.28	38.74	90	202.02	66.45	39.53	90	195.98
3	71.25	34.79	120	226.04	70.23	36.28	105	211.51
4	77.42	39.67	135	252.09	72.52	37.16	135	244.68
5	70.89	37.13	90	198.02	67.14	38.92	75	181.06

As shown in Table 2, the proposed algorithm outperforms the manual decision in terms of OB₁ and OB₃. As for OB₂, it is interesting that manual decision is slightly better than the proposed algorithm on three instances. This suggests that the proposed algorithm reduce the OB₁ and OB₃ by compromising OB₂. But in general, the sum of penalties can be reduced by using the proposed algorithm.

5 Conclusion

This paper studied a new optimization problem in integrated determining the CBCST arising from the production and operations management of steel plants. Optimal decision of CBCST is important to reduce the production costs of continuous caster and coordinate the production rhythm of the whole steel manufacturing process. To solve the problem, we proposed a hierarchical optimization method based on VNS. Experimental results on practical production data of a steel plant in China demonstrated that the proposed algorithm is effective for the integrated determination of CBCST problem. Further research will be focused on the development and application of the proposed algorithm.

Footnotes

Acknowledgments

This research is partially supported by the National Natural Science Foundation of China (51775112), the Research Program of Higher Education of Guangdong (2016KZDXM054, 2016KQNCX165), and the Science and Technology Planning Project of Guangdong (2014A010105058).

References

Box

R.E.

, Herbe

D.G.

, A scheduling model for LTV steel’s cleveland works’ twin strand continuous slab caster, Interfaces18 (1) (1988), 42–56.

Chang

S.Y.

, Chang

M.R.

, Hong

Y.H.

, A lot grouping algorithm for acontinuous slab caster in an integrated steel mill, Production Planning & Control11 (4) (2000), 363–368.

Tang

L.X.

, Wang

G.S.

, Decision support system for the batching problems of steelmaking and continuous-casting production, Omega-Int J Manage S36 (6) (2008), 976–991.

Tang

L.X.

, Luo

J.X.

, A new ILS algorithm for cast planningproblem in steel industry, Isij Int47 (3) (2007), 443–452.

Tang

L.X.

, Wang

G.S.

, Chen

Z.L.

, Integrated charge batching andcasting width selection at baosteel, Research62 (4) (2014), 772–787.

Xue

Y.C.

, Zheng

D.L.

, Yang

Q.W.

, Optimum steel making cast planwith unknown cast number based on the modified discrete particleswarm optimization, Control Theory & Applications27 (2) (2010), 273–277.

T.M.

, Chai

T.Y.

, Zheng

B.L.

, Model and algorithm forcontinuous casting batch production planning based on width flexibility, Journal of System Simulation23 (5) (2011), 1054–1058.

, Ledo

, Delgado

, Cerrada

, Pacheco

, Cabrera

, Sánchez

R.V.

and Valente de Oliveira

, A Bayesian approach toconsequent parameter estimation in probabilistic fuzzy systems andits application to bearing fault classification,, Knowledge-Based Systems129 (2017), 39–60.

, Sanchez

R.V.

, Zurita

, Cerrada

, Cabrera

and Vásquez

R.E.

, Multimodal deep support vector classification with homologous features and its application to gearbox fault diagnosis, Neurocomputing168 (2015), 119–127.

10.

Costa

E.B.M.

, Serra

G.L.O.

, Swarm optimization based adaptivefuzzy control design from robust stability criteria, Journal of Intelligent & Fuzzy Systems32 (2017), 1787–1804.

11.

Mladenovic

, Hansen

, Variable neighborhood search, Computers & Operations Research24 (11) (1997), 1097–1100.

12.

Hansen

, Mladenović

, Pérez

J.A.M.

, Variableneighbourhood search: Methods and applications, Annals of Operations Research175 (1) (2010), 367–407.

13.

Menéndez

, Bustillo

, Pardo

E.G.

, Duarte

, Generalvariable neighborhood search for the order batching and sequencing problem. European Journal of Operational Research263 (1) (2017), 82–93.

14.

Huang

K.W.

, Chen

J.L.

, Yang

C.S.

, Tsai

C.W.

, A memetic gravitation search algorithm for solving DNA fragment assembly problems, Journal of Intelligent & Fuzzy Systems30 (4) (2016), 2245–2255.

15.

Long

J.Y.

, Zheng

, Gao

X.Q.

, Dynamic scheduling insteelmaking-continuous casting production for continuous caster breakdown, International Journal of Production Research55 (11) (2017), 3197–3216.

16.

Pan

Q.K.

, Wang

, Mao

, Zhao

J.H.

, Zhang

, An effectiveartificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process, IEEE T Autom Sci Eng10 (2) (2013), 307–322.

17.

Long

J.Y.

, Zheng

, Gao

X.Q.

, Pardalos

P.M.

, A hybridmulti-objective evolutionary algorithm basedon NSGA-II for practical scheduling with release times in steelplants, Journal of the Operational Research Society67 (9) (2016), 1184–1199.

18.

Bai

, Sun

, Zeng

, Deng

, Li

, A multi-pattern deepfusion model for short-term bus passenger flow forecasting, Applied Soft Computing58 (2017), 669–680.

19.

Bektas

, The multiple traveling salesman problem: An overview offormulations and solution procedures, Omega-Int J Manage S34 (3) (2006), 209–219.

20.

Soylu

, A general variable neighborhood search heuristic formultiple traveling salesmen problem, Comput Ind Eng90 (C) (2015), 390–401.

21.

Clark

, Wright

J.W.

, Scheduling of vehicles from a centraldepot to a number of delivery points, Research12 (4) (1964), 568–581.

Instance ( $I * \tilde{I}$ )	CPLEX		VNS
	OB ₁	Solution time (s)	OB₁ (t_tvns = 2s)	OB₁ (t_tvns = 5s)	OB₁ (t_tvns = 8s)
60*10	50.84	3	57.17	51.86	51.26
60*20	35.34	7	39.51	38.04	36.57
60*30	45.32	105	49.64	47.25	47.25
80*10	34.68	3	37.06	34.68	34.68
80*20	31.39	14	35.17	33.98	32.75
80*30	41.39	115	48.72	44.32	43.75
100*10	28.95	4	31.24	29.89	29.57
100*20	31.80	19	35.53	34.67	33.54
100*30	39.98	98	45.91	43.14	42.54