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

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.

OPEN IN VIEWER

Fig.2

The procedure of VNS.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Fig.4

The neighborhood structures for solving CBCST problem.

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, ∑ 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 ′ = { α ii ′ ( | g i - g i ′ | ) if g i is compatible with g i ′ ∞ otherwise(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 ′ = { β ii ′ ( w i - w i ′ ) if 0 ≤ w i - w i ′ ≤ W ∞ otherwise(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 ′ = { γ ii ′ ( d i ′ - d i ) if d i - d i ′ ≤ 0 2 γ ii ′ ( d i - d i ′ ) otherwise(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

Min OB 1 = λ 1 ∑ i = 0 I ∑ i ′ = 0 I c ii ′ ∑ j = 1 J x ii ′ j + λ 2 ∑ i = 1 I d i ∑ j = 1 J y ij(4) subject to ∑ i = 0 I x ii ′ j = y i ′ j , ∀ i ′ ∈ { 0 , 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J }(5)∑ i ′ = 0 I x ii ′ j = y ij , ∀ i ∈ { 0 , 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J }(6)u ij - u i ′ j + n j x ii ′ j ≤ n j - 1 , ∀ i ∈ { 1 , 2 , … , I } , ∀ i ′ ∈ { 1 , 2 , … , I } , i ≠ i ′ , ∀ j ∈ { 1 , 2 , … , J }(7)1 ≤ u ij ≤ n j , ∀ i ∈ { 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J }(8)y 0 j = 1 , ∀ j ∈ { 1 , 2 , … , J }(9)∑ j = 1 J y ij ≤ 1 , ∀ i ∈ { 1 , 2 , … , I }(10)∑ i = 1 I y ij = n j , ∀ j ∈ { 1 , 2 , … , J }(11)x ii ′ j ∈ { 0 , 1 } , ∀ i ∈ { 0 , 1 , 2 , … , I } , ∀ i ′ ∈ { 0 , 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J } , i ≠ i ′(12)y ij ∈ { 0 , 1 } , ∀ i ∈ { 0 , 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J }(13)u ij ∈ N , ∀ i ∈ { 0 , 1 , 2 , … , I } , ∀ j ∈ { 1 , 2 , … , J }(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.

OPEN IN VIEWER

Fig.5

The neighborhood structures for solving charge selection and sequencing problem.

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 ∈ { 1 , 2 , … , I ˜ } , I ˜ is the total number of charges in all the casts ( I ˜ ≤ 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;

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

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

Ψ ˜ j : set of indices of all charges in cast j. For any j1 ≠ j2, Ψ ˜ j 1 ∩ Ψ ˜ j 2 = ∅ . ∑ j = 1 J | Ψ ˜ j | = 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 |, ∑ 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 = 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

Min OB 2 = λ 3 ∑ i ∈ Ψ ˜ ( max { 0 , s i + ct i - d i } - min { 0 , s i + ct i - d i } )(15) subject to s i ≥ et m , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ i ∈ Ψ ˜ j(16)s li ( j ) + ct li ( j ) + st ≤ s fi ( j ′ ) + ( 1 - h j , j ′ ) U , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(17)s li ( j ′ ) + ct li ( j ′ ) + st ≤ s fi ( j ) + h j , j ′ U , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(18)h j , j ′ + h j ′ , j = 1 , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(19)s i + ct i = s i + 1 , ∀ j ∈ { 1 , 2 , … , J } , ∀ i , i + 1 ∈ Ψ ˜ j(20)∑ i ∈ Ψ ˜ g i , r ≥ R - r + 1 , ∀ r = { 1 , 2 , … , R }(21)s i + ( 1 - g i , r ) U ≥ ht r + ft i , ∀ i ∈ Ψ ˜ , ∀ r = { 1 , 2 , … , R }(22)s i - g i , r U < ht r + ft i , ∀ i ∈ Ψ ˜ , ∀ r = { 1 , 2 , … , R }(23)s i ≥ 0 , ∀ i ∈ Ψ ˜(24)g i , r ∈ { 0 , 1 } , ∀ i ∈ Ψ ˜ , ∀ r = { 1 , 2 , … , R }(25)h j , j ′ ∈ { 0 , 1 } , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(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). ∑ i = i + 1 li ( j ) g i , r ≥ ( li ( j ) - i ) + ( g i , r - 1 ) U , ∀ j ∈ { 1 , 2 , … , J } , ∀ i ∈ { fi ( j ) , … , li ( j ) - 1 } , ∀ r = { 1 , 2 , … , R }(27)∑ i = fi ( j ) i - 1 g i , r ≤ g i , r U , ∀ j ∈ { 1 , 2 , … , J } , ∀ i ∈ { fi ( j ) + 1 , … , li ( j ) } , ∀ r = { 1 , 2 , … , R }(28)g li ( j ) , r ≤ g fi ( j ′ ) , r - h j , j ′ + 1 , ∀ r = { 1 , 2 , … , R } , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(29)g fi ( j ′ ) , r ≥ g li ( j ) , r + h j , j ′ - 1 , ∀ r = { 1 , 2 , … , R } , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(30)g li ( j ′ ) , r ≤ g fi ( j ) , r + h j , j ′ , ∀ r = { 1 , 2 , … , R } , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(31)g fi ( j ) , r ≥ g li ( j ′ ) , r - h j , j ′ , ∀ r = { 1 , 2 , … , R } , ∀ m ∈ { 1 , 2 , … , M } , ∀ j ∈ Ω m , ∀ j ′ ∈ Ω m , j ≠ j ′(32)

OPEN IN VIEWER

Fig.6

The graphical interpretation of the 6 valid inequalities.

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);

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 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 ∈ [ 40 , 44 ] , average processing time of charge i on CC2 ct i 2 ∈ [ 60 , 64 ] , average processing time of charge i on CC3 ct i 3 ∈ [ 46 , 51 ] , average processing time of charge i on CC4 ct i 4 ∈ [ 53 , 57 ] , average processing time of charge i on CC5 ct i 5 ∈ [ 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 / ∑ j = 1 J n j , λ 2 = 0.05 / ∑ j = 1 J n j , λ 3 = 0.2 / 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.

OPEN IN VIEWER

Fig.7

The box plots of the RPI values.

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 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 I ˜ = 10 ; J = 2, n _j  = 8 (j = 1) and n _j  = 12 (j = 2) are set for the instances with 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 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 ( I ˜ = 10 or 20) are solved efficiently by CPLEX. However, for those instances with 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.

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.

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.