Sage Journals: Discover world-class research

Abstract

Steelmaking-refining-Continuous Casting (SCC) is a key process in iron and steel production. SCC scheduling is to determine an optimal schedule for the SCC process, which is a worldwide and important problem. High-quality SCC scheduling methods will help to allocate production resources effectively and increase the productivity. However, dynamic events (e.g. machine breakdown) may happen in the realistic SCC process, which will make the SCC schedule inexecutable or not optimal. In this case, SCC rescheduling is essential in order to obtain a new optimal schedule suitable for the current production environments. The SCC rescheduling can be modeled as hybrid flowshop rescheduling. In this paper, an Improved Imperialist Competitive Algorithm (IICA) is proposed to address the SCC rescheduling. In the proposed IICA, an empire initialization is first devised for constructing an initial population with diversity and certain quality. Moreover, multiswap-based local search and imperialist competition are designed to improve the exploitation ability of the IICA, while revolution and restart strategy are devised to enhance the exploration ability of the IICA. Comparison experiments with three kinds of ICA have shown the efficiency of the IICA.

Keywords

Imperialist competitive algorithm steelmaking-refining-continuous casting iron and steel production hybrid flowshop rescheduling

Introduction

Iron and steel production supplies important materials for many industries. It has special characteristics such as high temperature, high weight, and high energy consumption.¹ Steelmaking-refining-Continuous Casting (SCC)² is the bottleneck of the iron and steel production process,^3,4 therefore, scheduling the SCC process, that is, SCC scheduling, is a key and complicated problem. The SCC scheduling is NP-hard,^1,5 and can be modeled as hybrid flowshop scheduling.^4,6 With respect to the hybrid flowshop scheduling, researchers can refer to Ribas et al.,⁷ Meng et al.,⁸ and Zhang et al.⁹ Powerful SCC scheduling methods will help to allocate production resources efficiently and improve the productivity.

Unfortunately, a number of dynamic events (e.g. machine breakdown, new order arrival, order cancellation) may happen in the realistic SCC process,¹⁰ which will make original SCC scheduling plans infeasible or not optimal. In this case, SCC rescheduling is essential to construct a new optimal schedule, which is suitable for current production environments. The SCC rescheduling can be modeled as hybrid flowshop rescheduling.^11–13 That is, the SCC rescheduling can be thought as the realistic application of the hybrid flowshop rescheduling.

Compared with fruitful research on the SCC scheduling, less attempts have been made on the SCC rescheduling.^11,14 Existing SCC rescheduling methods includes heuristics,¹⁵ Lagrangian relaxation,^14,16 and metaheuristics. Among the existing metaheuristics-based methods, Tang et al.¹⁰ designed a differential evolution with incremental mechanism, while Long et al.¹⁷ developed a hybrid algorithm which combined genetic algorithm and variable neighborhood search, where continuous caster breakdown was considered as the dynamic event. Li et al.¹¹ presented a hybrid fruit fly optimization algorithm, where processing times in the continuous casting stage were considered to be controllable. Peng et al.¹² devised an improved artificial bee colony.

Imperialist Competitive Algorithm (ICA) is a recent and effective metaheuristic,¹⁸ which has been employed to successfully address many NP-hard problems, such as assembly flowshop scheduling,¹⁹ energy-efficient flexible job shop scheduling,²⁰ and distributed shop scheduling.²¹ The ICA begins with an initial population of solutions (named countries). Countries are classified as imperialists or colonies. Each colony is assigned to exactly an imperialist. Each imperialist attempts to assimilate its colonies and also tries to possess more colonies from other imperialists.²² The basic ICA cannot be implemented directly to address the SCC rescheduling, since it is originally presented for continuous optimization problems. In this paper, an improved ICA is designed to solve the SCC rescheduling, named IICA.

The remainder of this paper is organized as follows. Section “SCC rescheduling problem” describes the SCC rescheduling problem. Section “Introduction of Basic ICA” describes the basic ICA. Section “Improved imperialist competitive algorithm” illustrates the details of the proposed IICA. Section “Experiment results” lists experiment comparison results. Finally, section “Conclusions” concludes this paper.

SCC rescheduling problem

In general, the SCC process contains three sequential production phases, i.e., steelmaking stage, refining stage, and continuous casting stage. In some cases, several refining stages may be contained in the SCC process, called multirefining. Each production stage has its own responsibility. More specifically, in the steelmaking stage, hot molten iron is transferred into molten steel and undesired impurity ingredients are lowered to certain levels. This is achieved by the machine named converter. The refining stage has the responsibility of further eliminating the impurity ingredients, and adding the required alloy ingredients. This is produced by the machine named refining furnace. In the continuous casting stage, liquid steel is casted into solid slabs, which is achieved by the machine named continuous caster. In the steelmaking and refining stage stages, charge is the basic production unit, while in the continuous casting stage, cast is the basic production unit.^4,5

Figure 1 illustrates the SCC process simply. As can be seen from Figure 1, the SCC process contains steelmaking stage, three refining stages, and continuous casting stage, where each stage contains three machines.

Figure 1.

Illustration of a SCC process.¹²

The real-world SCC process executes the production according to the original schedule which is determined before the production. However, at some time (say RT), some dynamic events happen, for example, machine breakdown, new order arrival or order cancellation. In this paper, machine breakdown (converter breakdown and refining furnace breakdown) is considered as the dynamic event. Under the circumstances, the original SCC schedule may become inexecutable, infeasible, or not optimal, which makes the SCC rescheduling essential. The SCC rescheduling may become is to reschedule the SCC process at RT (called rescheduling time) and regenerate a new optimal schedule with optimal values in efficiency objectives and system instability objectives, and it specifies that, for each unfinished charge, its starting times, completion times and machine allocation in each stage.¹² Meanwhile, the new optimal schedule must satisfy current production environments and a number of production constraints, for example, for each charge, the next operation can begin only after the preceding operation has finished and the charge has been transferred to the machine; for two consecutive charges processed by a machine, the next charge can begin only after the preceding charge has finished.⁴ More specifically, four efficiency objectives and two system instability objectives are considered, and the six objectives are weighted as the objective function in this paper, which is the same as Peng et al.¹² The corresponding mathematical model is somewhat similar to that in Peng et al.,¹² the difference between them is that, the processing times of the continuous casting stage are constant in this paper, while those are controllable in Peng et al.¹²

Introduction of Basic ICA

The basic ICA begins with empire initialization, which generates an initial population of N solutions (named countries). Among the N countries, the N_Imp best countries (named imperialists) are utilized to construct the empires (each imperialist corresponds to each empire), while the remaining N-N_Imp countries serve as colonies of the N_Imp empires. That is, an imperialist and its corresponding colonies together form an empire, while each colony belongs to and only belongs to an empire, and an empire may contain several colonies. The number of colonies allocated to imperialist i is determined by the fitness of the imperialist, denoted as NC_i. The fitter the imperialist i is, the bigger NC_i is. Then NC_i colonies are selected randomly for imperialist i. When the Empire initialization is finished, a cycle of Assimilation-Exchange of imperialist and colony-Imperialist competition-Elimination of powerless imperialists continues until stopping conditions are reached.¹⁸ More specifically, the basic ICA is displayed as follows.

Framework of the basic ICA
//Empire initialization Generate N countries, select N_Imp best countries as imperialists to construct the empires, and allocate the remaining N-N_Imp countries to the N_Imp empires as colonies. while termination condition has not been met //Assimilation For each colony, improve it by moving towards its relevant imperialist. //Exchange imperialist and colony For each imperialist, if the best one among its relevant colonies is better than it, exchange the best colony and the imperialist. //Imperialist competition Select one of the weakest colonies of the weakest empire, make a competition among all the empires to select an imperialist, the selected imperialist will possess the colony. //Elimination of powerless imperialists For each imperialist, the imperialist collapses if it lost all the colonies. end while

Framework of the basic ICA

//Empire initialization
Generate N countries, select N_Imp best countries as imperialists to construct the empires, and allocate the remaining N-N_Imp countries to the N_Imp empires as colonies.
while termination condition has not been met
//Assimilation
For each colony, improve it by moving towards its relevant imperialist.
//Exchange imperialist and colony
For each imperialist, if the best one among its relevant colonies is better than it, exchange the best colony and the imperialist.
//Imperialist competition
Select one of the weakest colonies of the weakest empire, make a competition among all the empires to select an imperialist, the selected imperialist will possess the colony.
//Elimination of powerless imperialists
For each imperialist, the imperialist collapses if it lost all the colonies.
end while

Improved imperialist competitive algorithm

The section introduces the details of the designed IICA. First, encoding and decoding is shown. Then, empire initialization, multiswap-based local search, assimilation, revolution, exchange of imperialist and colony, imperialist competition, and restart strategy, are illustrated sequentially. Finally, the framework of the IICA is described.

Encoding and decoding

Charge permutation is employed as the encoding. More specifically, the encoding method of Peng et al.¹² is utilized in the IICA. After the encoding method is decided, a decoding method should be determined, which will decode a solution to a schedule. The decoding method in Peng et al.¹² is modified for the IICA. The modification is that, the steps relevant to controllable processing times are removed. More specifically, the decoding method of the IICA includes forward decoding and backward decoding. The forward decoding is the same as that of Peng et al.,¹² while the backward decoding is some different, where the difference is mainly that, the charge left-shifting strategy and processing time adding strategy in Peng et al.¹² are not implemented in the IICA.

Empire initialization

An initial population with certain quality may be beneficial to enhance the performance of the IICA. In this paper, an empire initialization is specially devised for obtaining a population with diversity and certain quality. Let N_h denote the number of countries obtained by heuristic instead of random generation, the empire initialization can be given as follows.

Step 1. Generate two countries C₁ and C₂ by sequencing charges in non-decreasing order based on the starting times at refining and continuous casting stage, respectively.

Step 2. Set i = 3.

Step 3. If i≤N_h, randomly initialize country C_i to be C₁ and C₂ with equal probability, and then execute multiswap or Insert operator to C_i with equal probability, go to Step 4; Otherwise, go to Step 5.

Step 4. Set i = i+1, and go to Step 3.

Step 5. Generate the remaining N-N_h countries randomly.

Step 6. Sort all the countries, and select the N_Imp best countries to be the imperialists, which correspond to N_Imp empires. The number of colonies allocated to the j^th empire (say NC_j) is determined by Formula (1).

N C_{j} = \frac{j^{- α}}{\sum_{k = 1}^{N_{Imp}} k^{- α}}

(1)

where α is a positive real number²³ and set to be 1.5 in this paper.

Step 7. For each imperialist (say j), select NC_j countries randomly and allocate them as colonies of the empire j.

Multiswap-based local search

To improve the exploitation ability of the IICA, a multiswap-based local search is developed to further improve the imperialists. Let Q be the allowed maximum number, the multiswap-based local search is illustrated as follows.

Step 1. Set i = 1.

Step 2. Set q = 1.

Step 3. If q≤Q, execute a multiswap operator to the imperialist I_i, if the obtained solution is better than I_i, update I_i; Otherwise, go to Step 5.

Step 4. Set q=q+1, go to Step 3.

Step 5. Set i=i+1, if i≤N_Imp, go to Step 2; Otherwise, stop.

Assimilation

The assimilation is to improve each colony by moving toward its corresponding imperialist. Let NI_k denote the number of successive iterations that colony C_k has not been improved, the assimilation is devised as follows.

Step 1. For each colony C_k (k = 1,2,…,N-N_Imp), execute Partially Mapped Crossover (PMX) to C_k and its corresponding imperialist, then two new solutions are obtained, denoted as P₁ and P₂.

Step 2. Select randomly a solution from P₁ and P₂ with equal probability, say P_t (t = 1 or 2).

Step 3. If P_t is better than C_k, update C_k by P_t, and set NI_k = 0; Otherwise, go to Step 4.

Step 4. If f(P_t)=f(C_k), update C_k by P_t, set NI_k = NI_k+1, where f(P_t) and f(C_k) denote the objective value of P_t and C_k respectively; Otherwise, go to Step 5.

Step 5. Set NI_k = NI_k+1, accept P_t as C_k with the probability $\exp (- (f (P_{t}) - f (C_{k})) / TP)$ , where

$TP = \frac{\sum_{p = 1}^{M} \sum_{s = 1}^{S} P T_{ps}}{M \cdot S \cdot 10} \cdot T$ , M and S denote the number of charges and stages respectively, PT_ps denotes the processing time of charge p at the sth stage, T is set to be 0.4.

Revolution

In the basic ICA, revolution is not contained. Revolution was initially devised by Shokrollahpour et al.,¹⁹ that is, in each iteration, some of the weakest colonies are selected and replaced with new solutions, randomly, where replacement rate is called revolution rate. In this paper, revolution is specially designed. Let Rr denote the revolution rate, ls denote the size of local search, the steps of the revolution are as follows.

Step 1. For each imperialist I_i (i = 1,2,…,N_Imp), a number rn is generated randomly in [0,1], if rn < Rr, go to Step 1.1; Otherwise, set i = i+1.

Step 1.1. Generate randomly ls solutions (Say S₁, S₂,…, S_ls). For each solution S_p (p = 1,2,…,ls), set S_p = I_i, and execute multiswap to S_k.

Step 1.2. If the best one of the new ls solutions is better than I_j, update I_j.

Step 2. For colony C_k (k = 1,…,N−N_Imp), a number rn is generated randomly in [0,1], if rn < Rr, go to Step 2.1; Otherwise, set k = k+1.

Step 2.1. Generate randomly ls solutions (Say S₁, S₂,…, S_ls). For each solution S_q (q = 1,2,…,ls), set S_q = C_k, and execute multiswap to S_q.

Step 2.2. If the best one of the new ls solutions (denoted as S_r) is better than C_k, update C_k by S_r, and set NI_k=0; Otherwise, go to Step 2.3.

Step 2.3. If f(S_r)=f(C_k), update C_k by S_r, where f(S_r) and f(C_k) denote the objective value of S_r and C_k, respectively, and set NI_k=NI_k+1; Otherwise, go to Step 2.4.

Step 2.4. Set NI_k = NI_k+1, accept S_r as C_k with the probability $\exp (- (f (S_{r}) - f (C_{k})) / TP)$ , where $TP = \frac{\sum_{p = 1}^{M} \sum_{s = 1}^{S} P T_{ps}}{M \cdot S \cdot 10} \cdot T$ , M and S denote the number of charges and stages respectively, PT_ps denotes the processing time of charge p at the sth stage, T is set to be 0.4.

Exchange imperialist and colony

For each empire (say j), if the best one among its colonies (say colony C_k) is better than imperialist I_j, exchange I_j and C_k. The operator is to make sure that the imperialist is better than the colonies in the empire, which can further guide the evolution of its corresponding colonies to more promise area.

Imperialist competition

In the basic ICA, the imperialist competition is executed in each iteration. However, we believe that it is not necessary to employ the imperialist competition in each iteration. This is because, a colony may not be improved in one iteration, however, it may be a promising solution and can be further improved in the following several iterations. Therefore, an imperialist competition is devised in this paper, that is, execute the imperialist competition for R iterations instead of one iteration. Let Iter be the iteration number, the steps of the imperialist competition can be listed as follows.

Step 1. If Iter is multiples of R, that is, Iter%R = 0, go to Step 2; Otherwise, stop.

Step 2. If the weakest empire (say j) has lost all of its colonies, select an imperialist randomly (say p), allocate imperialist I_j to I_p as a colony, stop; Otherwise, go to Step 3.

Step 3. Select randomly one colony from empire j, select an imperialist randomly (say p), allocate the colony to I_p.

Step 4. If empire j has lost all of its colonies, allocate the imperialist I_j to I_p as a colony.

Restart strategy

In the evolutionary process of the IICA, some colony may encounter such a situation that has not been improved during the last several successive iterations. This may mean that the colony has been trapped in the local optimum. To escape the local optimum, a restart strategy is devised in this paper. Let NI_max be the allowed number of successive iterations that a colony has not been improved, LS be the size of local search, the restart strategy is illustrated as follows:

Step 1. For colony C_k (k = 1,…,N−N_Imp), if NI_k > NI_max, go to Step 2; Otherwise, stop.

Step 2. Construct randomly LS solutions (Say S₁, S₂,…, S_LS), and for each solution S_p (p = 1,2,…, LS), set S_p to be the best solution found so far G_b, execute several multiswap to S_p.

Step 3. Find the best one among the obtained LS solutions (denoted by S_b), set C_k = S_b. If S_b is better than G_b, update G_b.

Framework of the proposed IICA

Let N and N_Imp be the number of countries and imperialists, respectively, Rr be the revolution rate, NI_max be the allowed number of successive non-improving iterations, R be the parameter in the imperialist competition, G_b be the best solution found so far, and Iter be the iteration number. The framework of the IICA is stated as follows.

Framework of the IICA
Step 1. Set Iter = 1. Step 2.Empire initialization. Generate N_h countries by the heuristic presented in section “Empire initialization,” and generate N-N_h countries randomly. Select N_Imp best countries as imperialists to construct the empires, and allocate randomly the remaining N-N_Imp countries to the N_Imp imperialists as colonies according to Formula (1). If an imperialist (Say I_i) has not been allocated any colony, select an imperialist randomly (Say I_j) and allocate I_i to I_j as a colony. Find the best one among the N countries, utilize it to initialize G_b. Step 3.Multiswap-based local search. For each imperialist, execute a multiswap operator to it, if a better solution can be obtained, utilize it to replace the imperialist, continue the step until a predefined number is reached. If the updated imperialist is better than G_b, update G_b. Step 4.Assimilation. For each colony, execute PMX to the colony and its corresponding imperialist, then two new solutions are obtained, selected one from the two solutions, and further determine whether it can be accepted as the colony. Step 5.Exchange imperialist and colony. For each empire, if the best one among its colonies is better than the imperialist, exchange the colony and the imperialist. If a solution better than G_b is found, update G_b. Step 6.Revolution. For each imperialist, execute the revolution strategy described in section “Revolution.” For each colony, execute the revolution strategy described in section “Revolution.” Step 7.Exchange imperialist and colony. For each empire, if the best one among its colonies is better than the imperialist, exchange the colony and the imperialist. If a solution better than G_b is found, update G_b by the solution. Step 8.Imperialist competition. If Iter is multiples of R, select randomly one colony of the weakest empire (say j), select an imperialist randomly (say p), allocate the colony to imperialist I_p. If empire j has lost all of its colonies, allocate the imperialist I_j to I_p as a colony. Step 9.Restart strategy. For each colony, if it has not been improved during the last NI_max iterations, construct LS solutions, which are copies of G_b. Execute several multiswap to each solution. Utilize the best one of the obtained LS solutions update the colony. If a solution better than G_b is found, update G_b by the solution. Step 10.Set Iter = Iter+ l. If the termination condition (e.g. allowed elapsed CPU time) has been met, return G_b. Otherwise go to Step 3.

Framework of the IICA

Step 1. Set Iter = 1.
Step 2.Empire initialization. Generate N_h countries by the heuristic presented in section “Empire initialization,” and generate N-N_h countries randomly. Select N_Imp best countries as imperialists to construct the empires, and allocate randomly the remaining N-N_Imp countries to the N_Imp imperialists as colonies according to Formula (1). If an imperialist (Say I_i) has not been allocated any colony, select an imperialist randomly (Say I_j) and allocate I_i to I_j as a colony. Find the best one among the N countries, utilize it to initialize G_b.
Step 3.Multiswap-based local search. For each imperialist, execute a multiswap operator to it, if a better solution can be obtained, utilize it to replace the imperialist, continue the step until a predefined number is reached. If the updated imperialist is better than G_b, update G_b.
Step 4.Assimilation. For each colony, execute PMX to the colony and its corresponding imperialist, then two new solutions are obtained, selected one from the two solutions, and further determine whether it can be accepted as the colony.
Step 5.Exchange imperialist and colony. For each empire, if the best one among its colonies is better than the imperialist, exchange the colony and the imperialist. If a solution better than G_b is found, update G_b.
Step 6.Revolution. For each imperialist, execute the revolution strategy described in section “Revolution.” For each colony, execute the revolution strategy described in section “Revolution.”
Step 7.Exchange imperialist and colony. For each empire, if the best one among its colonies is better than the imperialist, exchange the colony and the imperialist. If a solution better than G_b is found, update G_b by the solution.
Step 8.Imperialist competition. If Iter is multiples of R, select randomly one colony of the weakest empire (say j), select an imperialist randomly (say p), allocate the colony to imperialist I_p. If empire j has lost all of its colonies, allocate the imperialist I_j to I_p as a colony.
Step 9.Restart strategy. For each colony, if it has not been improved during the last NI_max iterations, construct LS solutions, which are copies of G_b. Execute several multiswap to each solution. Utilize the best one of the obtained LS solutions update the colony. If a solution better than G_b is found, update G_b by the solution.
Step 10.Set Iter = Iter+ l. If the termination condition (e.g. allowed elapsed CPU time) has been met, return G_b. Otherwise go to Step 3.

Experiment results

The main concern of applying the metaheuristics to solve the combinatorial optimization problems is the solution quality. In this paper, to show the effectiveness of the presented IICA, three kinds of ICA in the literature are employed for comparison. The three kinds of ICA are listed as follows, (1) the basic ICA¹⁸ (ICA), (2) an improved ICA devised by Shokrollahpour et al.¹⁹ (ICA_S), and (3) hybrid ICA proposed by Ghasemishabankareh et al.²⁴ (HICA). Note that the PMX operator is employed for the ICA and HICA, since the corresponding assimilation operation is not suitable for the SCC rescheduling. More specifically, for each colony, execute the PMX to it and its corresponding imperialist, which generates two solutions, select randomly a solution from the two solutions with equal probability. In the ICA_S, two assimilation operations are tested, that is, (1) assimilation operation 1: the same assimilation operator employed for the ICA and HICA stated above; and (2) assimilation operation 2: the assimilation operation in the corresponding reference. Moreover, for the ICA_S utilizing each assimilation operation, two revolution cases are tested, that is (1) revolution strategy 1: the 20% worst colonies are implemented the revolution; and (2) revolution strategy 2: the 30% worst colonies are implemented the revolution. That is, four versions of ICA_S are tested in this paper, which are named ICA_S1, ICA_S2, ICA_S3, ICA_S4, respectively. Specifically, the ICA_S1 is equipped with assimilation operation 1 and revolution strategy 1, while the ICA_S2 is equipped with assimilation operation 1 and revolution strategy 2. The ICA_S3 is equipped with assimilation operation 2 and revolution strategy 1, while ICA_S4 is equipped with assimilation operation 2 and revolution strategy 2.

We code the above seven compared algorithms (i.e. IICA, ICA, HICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4) in C++, and run them on a 2.13 GHZ computer with 2G RAM using Windows 7 Operation System. The elapsed CPU time is set to be termination condition. Three termination conditions are used in this paper, that is, 10, 20, and 30 s. For each termination condition, each compared algorithm is run 10 times independently, the average result of the ten runs is calculated, and further served as the performance of the algorithm. Relative percentage increase (RPI) is calculated for comparing these algorithms, which is calculated by Formula (2).

RPI = \frac{f_{ca} - f_{lb}}{f_{lb}} \cdot 100 %

(2)

where f_ca denotes the average objective function value of IICA, ICA, ICA_S, or HICA, and f_lb denotes the best one among f_ca (ca denotes IICA, ICA, ICA_S, HICA).

Test instances

Thirty test instances are randomly generated based on the test instance generation method in Pan et al.,⁴ and are further used to compare the above algorithms. More specifically, the SCC process contains steelmaking stage, refining stage, and continuous casting stage. The three stages contain three converts, five refining furnaces, and four continuous casters, respectively. Each continuous caster produces 3 to 4 casts in each workday, where each cast processes 8 to 12 charges. The processing time of each charge in the steelmaking stage is 38, while the processing times of each charge in the refining stage and continuous casting stage are in [36,50] and [38,44], respectively. The transferring time between the steelmaking stage and refining stage is in [10,15], which is the same as that between the refining stage and continuous casting stage.

With respect to the dynamic event, machine breakdown is considered, for each test instance, two machine breakdown cases are generated randomly, that is (1) converter breakdown: (i) breakdown converter: a converter is selected randomly (say c); (ii) rescheduling time, the rescheduling time is equal to RT₁+RT₂, where RT₁ is 10% of the completion time on the converter c, and RT₂ is the starting time of the first charge processed on the converter c; (iii) breakdown duration: breakdown duration is equal to 6% of the machine completion time of the converter c. (2) refining furnace breakdown: (i) breakdown refining furnace: a refining furnace is selected randomly (say rf); (ii) rescheduling time, the rescheduling time is equal to RT₃+RT₄, where RT₃ is 30% of the completion time of the refining furnace rf, and RT₄ is the starting time of the first charge processed on the refining furnace rf; (iii) breakdown duration: breakdown duration is equal to 6% of the machine completion time of the refining furnace rf.

Therefore, under each termination condition, for each machine breakdown case of each test instance, each compared algorithm is run 10 times independently, the average result of the 10 runs is calculated, and RPI can be further calculated. Then two RPIs can be obtained for two machine breakdown cases of each test instance. The average value of two RPIs is employed as the average RPI of each compared algorithm.

Comparison results

In this section, the IICA is compared with the ICA, HICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4. In the IICA, the main parameters stated in section “Framework of the proposed IICA,” that is N, N_Imp, Rr, NI_max, and R are set to be 80, 6, 0.3, 500, and 20, respectively. To make the comparison fair, the same termination condition is used, that is, allowed CPU time. CPU time 10 s is employed first. Table 1 lists the average RPI comparison results of the seven algorithms when CPU time = 10 s. From Table 1, it can be noticed that the IICA and HICA perform better than ICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4, and the IICA is worse than the HICA. More specifically, the average RPIs of IICA and HICA are 1.56% and 0.65%, respectively, while the average RPIs of the ICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4 are 25.13%, 27.17%, 26.72%, 32.06%, and 32.06%, respectively.

Table 1.

The average RPI values when CPU time = 10 s.

Instance	ICA	HICA	ICA_S1	ICA_S2	ICA_S3	ICA_S4	IICA
1	45.85	0.29	48.15	47.82	51.85	51.85	2.74
2	14.27	0.00	14.09	14.28	17.15	17.15	1.47
3	20.47	1.26	22.01	21.93	24.71	24.71	1.14
4	26.92	0.00	28.41	28.12	31.43	31.43	2.24
5	37.56	0.21	44.11	43.17	49.79	49.79	3.65
6	35.86	0.00	36.87	36.23	40.29	40.29	2.72
7	38.70	0.88	44.72	46.90	69.96	69.96	2.88
8	22.68	0.22	23.98	23.71	26.35	26.35	1.31
9	18.76	0.00	25.95	23.37	33.47	33.47	1.09
10	18.93	0.00	19.89	19.15	23.22	23.22	2.46
11	21.18	1.50	23.56	22.17	25.42	25.42	0.31
12	39.91	0.00	40.31	39.45	45.78	45.78	3.58
13	17.86	0.00	18.09	18.26	23.91	23.91	1.20
14	19.63	1.38	21.67	21.86	25.37	25.37	0.25
15	19.94	0.91	26.60	22.73	36.78	36.78	0.22
16	43.73	3.49	45.15	44.17	54.66	54.66	0.51
17	23.76	5.40	25.73	25.74	30.96	30.96	0.23
18	22.03	2.09	22.12	21.98	23.58	23.58	1.38
19	26.16	0.00	29.03	28.13	32.86	32.86	3.63
20	14.44	0.00	16.83	17.46	21.11	21.11	1.58
21	17.63	0.00	21.19	19.96	25.38	25.38	0.88
22	29.77	0.00	32.57	32.87	35.98	35.98	1.68
23	27.61	0.09	28.06	28.67	32.38	32.38	0.31
24	30.67	0.00	30.37	30.93	34.32	34.32	2.67
25	19.71	0.00	21.66	21.11	24.01	24.01	3.07
26	14.57	0.00	15.33	16.11	19.94	19.94	1.72
27	18.37	0.00	18.22	17.78	20.95	20.95	1.08
28	31.07	0.08	30.96	28.92	37.55	37.55	0.38
29	21.60	1.73	23.53	22.78	25.30	25.30	0.00
30	14.46	0.00	15.91	15.97	17.42	17.42	0.33
Average	25.13	0.65	27.17	26.72	32.06	32.06	1.56

Moreover, the termination condition is set to be longer CPU time, that is, 20 s. Table 2 gives the corresponding average RPI comparison values of these compared algorithms. Table 2 shows that the IICA performs better than other algorithms, that is, the HICA, ICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4. Precisely, the average RPI of IICA is 0.69%, while the average RPIs of the ICA, HICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4 are 22.69%, 1.03%, 24.61%, 23.94%, 33.30%, and 33.30%, respectively.

Table 2.

The average RPI values when under CPU time = 20 s.

Instance	ICA	HICA	ICA_S1	ICA_S2	ICA_S3	ICA_S4	IICA
1	47.01	0.48	42.82	42.31	53.05	53.05	1.98
2	14.51	0.00	12.49	11.73	17.39	17.39	0.70
3	22.39	2.35	21.93	21.09	26.70	26.70	0.00
4	27.47	0.00	25.78	25.44	31.99	31.99	0.96
5	39.00	0.51	40.23	39.65	51.37	51.37	2.61
6	36.32	0.00	33.80	32.06	40.77	40.77	1.64
7	43.45	3.07	43.53	42.91	75.50	75.50	0.38
8	23.38	0.36	21.26	20.22	27.07	27.07	0.53
9	19.07	0.07	18.88	19.13	33.82	33.82	0.68
10	19.55	0.19	18.56	17.89	23.87	23.87	0.96
11	22.86	2.59	22.42	21.74	27.17	27.17	0.00
12	41.08	0.04	35.73	35.43	47.01	47.01	1.65
13	18.48	0.03	15.14	14.37	24.57	24.57	0.22
14	20.83	2.01	19.70	20.56	26.63	26.63	0.20
15	20.73	1.47	19.93	19.20	37.62	37.62	0.00
16	47.59	5.05	43.32	43.21	58.89	58.89	0.33
17	24.89	5.02	22.92	23.12	32.17	32.17	0.36
18	23.26	2.44	20.92	20.67	24.83	24.83	0.59
19	26.82	0.40	25.42	22.66	33.56	33.56	1.55
20	14.87	0.00	15.22	15.44	21.57	21.57	0.64
21	18.54	0.21	18.75	17.30	26.35	26.35	0.00
22	31.08	0.44	31.06	29.61	37.34	37.34	0.89
23	30.09	1.18	26.49	26.75	34.93	34.93	0.00
24	31.34	0.00	28.40	27.92	35.01	35.01	0.75
25	20.68	0.00	20.14	19.55	25.02	25.02	1.24
26	15.00	0.13	13.91	13.39	20.42	20.42	1.25
27	18.61	0.00	15.86	15.49	21.19	21.19	0.42
28	32.63	0.82	27.52	25.39	39.19	39.19	0.00
29	22.20	1.83	21.20	19.51	25.92	25.92	0.00
30	15.17	0.33	15.11	14.40	18.15	18.15	0.17
Average	22.69	1.03	24.61	23.94	33.30	33.30	0.69

Finally, CPU time 30 s is used as the termination condition. Table 3 describes the corresponding average RPI comparison values. According to Table 3, it can be noticed that the IICA also performs best among the seven algorithms. The average RPIs of the IICA, ICA, HICA, ICA_S1, ICA_S2, ICA_S3, and ICA_S4 are 0.58%, 27.04%, 1.19%, 22.75%, 21.64%, 34.10%, and 34.10%, respectively.

Table 3.

The average RPI values when CPU time = 30 s.

Instance	ICA	HICA	ICA_S1	ICA_S2	ICA_S3	ICA_S4	IICA
1	47.43	0.42	39.20	35.47	53.50	53.50	1.54
2	14.93	0.18	11.44	9.83	17.82	17.82	0.81
3	24.44	3.83	21.76	20.73	28.81	28.81	0.00
4	28.95	0.00	24.27	23.88	33.51	33.51	1.46
5	39.85	0.49	37.26	34.81	52.31	52.31	2.39
6	36.88	0.00	29.28	28.79	41.35	41.35	1.68
7	45.32	2.79	40.86	40.97	77.81	77.81	0.03
8	23.66	0.32	19.74	17.97	27.36	27.36	0.40
9	19.90	0.42	17.32	15.95	34.74	34.74	0.87
10	19.98	0.39	17.41	16.32	24.31	24.31	0.18
11	23.96	3.35	21.78	20.72	28.32	28.32	0.00
12	41.94	0.00	33.62	33.12	47.89	47.89	1.19
13	19.50	0.22	13.68	12.69	25.63	25.63	0.47
14	21.51	2.06	18.44	18.81	27.35	27.35	0.05
15	21.14	1.79	18.12	16.08	38.05	38.05	0.00
16	48.47	4.91	40.96	41.04	59.86	59.86	0.00
17	26.53	5.84	22.02	22.05	33.95	33.95	0.22
18	23.52	2.26	19.58	19.03	25.10	25.10	0.57
19	27.91	0.50	23.85	21.24	34.70	34.70	1.82
20	14.98	0.00	14.25	13.77	21.68	21.68	0.50
21	18.72	0.21	16.36	15.56	26.55	26.55	0.00
22	32.18	0.72	29.86	26.26	38.48	38.48	0.74
23	30.82	0.94	24.09	24.70	35.69	35.69	0.05
24	31.98	0.23	25.58	24.88	35.67	35.67	0.47
25	21.64	0.68	19.15	18.76	26.02	26.02	0.78
26	15.31	0.28	11.75	11.54	20.74	20.74	1.14
27	19.07	0.00	14.08	13.41	21.66	21.66	0.16
28	33.19	1.07	24.80	20.80	39.78	39.78	0.00
29	22.32	1.55	18.94	17.42	26.04	26.04	0.00
30	15.34	0.21	13.10	12.58	18.32	18.32	0.05
Average	27.04	1.19	22.75	21.64	34.10	34.10	0.58

According to the comparison results under three levels of CPU time, one can find that the IICA and HICA always outperform the remaining algorithms. Moreover, under shorter CPU time (i.e. 10 s), the performance of the IICA is worse than that of the HICA, while under longer CPU time (i.e. 20 and 30 s), the IICA outperforms the HICA. In conclusion, the above experimental results and analysis have shown that the IICA is an effective method for addressing the SCC rescheduling problem.

Conclusions

In the paper, we present an improved ICA for the SCC rescheduling, which can be recognized as the realistic application of the hybrid flowshop rescheduling. An empire initialization is devised to construct the initial countries with diversity and certain quality. Meanwhile, multiswap-based local search and imperialist competition are designed to enhance the intensification of the IICA. Moreover, revolution and restart strategy are devised to improve the diversification. In the future work, the IICA can be further enhanced by designing more effective operators based on problem characteristics or attempting to combining with other techniques.^25,26 Meanwhile, the IICA can be employed for addressing other production scheduling problems, for example, welding shop scheduling,^27,28 energy-efficient scheduling,^29,30 distributed scheduling,^31–33 integrated process planning and scheduling.³⁴ Furthermore, the existing rescheduling methods for the hybrid flowshop can be modified and adopted for the SCC rescheduling.

Footnotes

Authors’ Note

Kunkun Peng is also affiliated with State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, China.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This project is supported by National Natural Science Foundation of China (Grant No. 51705177, 51905199, 61773269).

ORCID iD

Chunjiang Zhang

References

Cui

Luo

. An improved Lagrangian relaxation approach to scheduling steelmaking-continuous casting process. Comput Chem Eng 2017; 106: 133–146.

García-Menéndez

Morán-Palacios

Ortega-Fernández

, et al. Scheduling in continuous steelmaking casting: a systematic review. ISIJ Int 2020; 60(6): 1097–1107.

Peng

Pan

Zhang

. An improved artificial bee colony algorithm for steelmaking-refining-continuous casting scheduling problem. Chin J Chem Eng 2018; 26(8): 1727–1735.

Pan

Wang

Mao

, et al. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Trans Autom Sci Eng 2013; 10(2): 307–322.

Jiang

Zheng

Liu

. A preference-inspired multi-objective soft scheduling algorithm for the practical steelmaking-continuous casting production. Comput Ind Eng 2018; 115: 582–594.

Jiang

Liu

Hao

. A two-phase soft optimization method for the uncertain scheduling problem in the steelmaking industry. IEEE Trans Syst Man Cybern-Syst 2017; 47(3): 416–431.

Ribas

Leisten

Framiñan

. Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res 2010; 37(8): 1439–1454.

Meng

Zhang

Shao

, et al. Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines. Int J Prod Res 2019; 57(4): 1119–1145.

Zhang

Pan

Gao

, et al. A three-stage multiobjective approach based on decomposition for an energy-efficient hybrid flow shop scheduling problem. IEEE Trans Syst Man Cybern-Syst 2019; Epub ahead of print May 2019. DOI: 10.1109/tsmc.2019.2916088.

10.

Tang

Zhao

Liu

. An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production. IEEE Trans Evol Comput 2014; 18(2): 209–225.

11.

Pan

Mao

. A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems. IEEE Trans Autom Sci Eng 2016; 13(2): 932–949.

12.

Peng

Pan

Gao

, et al. An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in steelmaking-refining-continuous casting process. Comput Ind Eng 2018; 122: 235–250.

13.

Peng

Pan

Gao

, et al. A multi-start variable neighbourhood descent algorithm for hybrid flowshop rescheduling. Swarm Evol Comput 2019; 45: 92–112.

14.

Sun

Ying

Luan

, et al. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. J Ind Manag Optim 2017; 13(3): 1431–1448.

15.

Chai

Tang

. An effective heuristic rescheduling method for steelmaking and continuous casting production process with multirefining modes. IEEE Trans Syst Man Cybern-Syst 2016; 46(12): 1675–1688.

16.

Mao

Pan

Pang

, et al. An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process. Control Eng Practice 2014; 30: 67–77.

17.

Long

Zheng

Gao

. Dynamic scheduling in steelmaking-continuous casting production for continuous caster breakdown. Int J Prod Res 2017; 55(11): 3197–3216.

18.

Atashpaz-Gargari

Lucas

. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. In: 2007 IEEE congress on evolutionary computation (CEC 2007), Singapore, 25–28 September 2007, pp. 4661–4667. New York: IEEE.

19.

Shokrollahpour

Zandieh

Dorri

. A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem. Int J Prod Res 2011; 49(11): 3087–3103.

20.

Lei

Wang

. A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold. IEEE T Cybern 2019; 49(3): 1097–1109.

21.

Lei

Yuan

Cai

, et al. An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling. Int J Prod Res 2020; 58(2): 597–614.

22.

Lian

Zhang

Gao

, et al. Integrated process planning and scheduling using an imperialist competitive algorithm. Int J Prod Res 2012; 50(15): 4326–4343.

23.

Lü

Huang

. Iterated tabu search for identifying community structure in complex networks. Phys Rev E 2009; 80(2): 026130.

24.

Ghasemishabankareh

Shahsavari-Pour

Basiri

, et al. A hybrid imperialist competitive algorithm for the flexible job shop problem. In: Australasian conference on artificial life and computational intelligence, 2 February 2016, pp. 221–233. Cham: Springer.

25.

Wen

Gao

. A transfer convolutional neural network for fault diagnosis based on ResNet-50. Neural Comput Appl 2020; 32: 6111–6124.

26.

Wen

Gao

. A new automatic machine learning based hyperparameter optimization for workpiece quality prediction. Meas Control. Epub ahead of print July 2020. DOI: 10.1177/0020294020932347.

27.

Gao

, et al. An effective multiobjective algorithm for energy-efficient scheduling in a real-life welding shop. IEEE Trans Ind Inform 2018; 14(12): 5400–5409.

28.

Gao

, et al. A multi-objective approach to welding shop scheduling for makespan, noise pollution and energy consumption. J Clean Prod 2018; 196: 773–787.

29.

Zhang

Pan

Gao

, et al. A multiobjective evolutionary algorithm based on decomposition for hybrid flowshop green scheduling problem. Comput Ind Eng 2019; 136: 325–344.

30.

Meng

Zhang

Shao

, et al. MILP models for energy-aware flexible job shop scheduling problem. J Clean Prod 2019; 210: 710–723.

31.

Pan

Gao

Wang

, et al. Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Syst Appl 2019; 124: 309–324.

32.

Ruiz

Pan

Naderi

. Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega-Int J Manage Sci 2019; 83: 213–222.

33.

Wang

Gao

, et al. Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm. Swarm Evol Comput 2020; 57: 100716.

34.

Gao

Pan

, et al. An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE Trans Syst Man Cybern-Syst2019; 49(10): 1933–1945.

An improved imperialist competitive algorithm for hybrid flowshop rescheduling in steelmaking-refining-continuous casting process

Abstract

Keywords

Introduction

SCC rescheduling problem

Introduction of Basic ICA

Improved imperialist competitive algorithm

Encoding and decoding

Empire initialization

Multiswap-based local search

Assimilation

Revolution

Exchange imperialist and colony

Imperialist competition

Restart strategy

Framework of the proposed IICA

Experiment results

Test instances

Comparison results

Conclusions

Footnotes

Authors’ Note

Declaration of conflicting interests

Funding

ORCID iD

References