An Improved Artificial Bee Colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process
Introduction
Hybrid Flowshop (HFS) scheduling is a complex decision-making process for deciding allocation to which machine in each stage for all the jobs and the sequence of jobs for each machine (Ruiz & Vázquez-Rodríguez, 2010), which is one of the most studied scheduling problems since it has significant applications in realistic production systems, e.g. iron and steel production, metal-forming, electronics, paper, and textile (Ribas et al., 2010, Ruiz and Vázquez-Rodríguez, 2010). Effective HFS scheduling methods are crucial to improve production efficiency, and thus make significant monetary savings. Meanwhile, the HFS scheduling problem is well known to be NP-hard (Tang & Wang, 2010). The problem has attracted a lot of research interest in recent years (Khalouli et al., 2010, Ruiz and Vázquez-Rodríguez, 2010, Ruiz et al., 2008).
Compared with classical HFS scheduling, real-world HFS scheduling is much more sophisticated, since a number of unexpected disruptions are involved in real-world scenarios, which may invalidate original schedules, e.g. machine breakdown, new job arrival, job cancellation (Katragjini et al., 2013, Katragjini et al., 2015, Tang, Zhao et al., 2014). Thus, HFS rescheduling becomes essential, which repairs the original schedule or regenerates a new optimal schedule (Ouelhadj and Petrovic, 2009, Vieira et al., 2003). In recent years, scientists of related research fields have paid more attention to HFS rescheduling problems with different disruptions. Zandieh and Gholami (2009) proposed an immune algorithm to handle HFS rescheduling with sequence-dependent setup times considering random machine breakdown. Tang, Liu, and Liu (2005) developed a neural network model and algorithm for HFS rescheduling with dynamic job arrivals. Wang and Choi, 2011, Choi and Wang, 2012 proposed decomposition-based approaches to handle HFS rescheduling with random machine breakdown and stochastic processing times, respectively. Very recently, Li, Pan, and Mao (2015) addressed a realistic flowshop rescheduling considering simultaneously five kinds of disruptions, i.e. machine breakdown, job processing time variation, job release variation, job cancellation, and new job arrival, they established a mathematical model and solved the problem by devising a hybrid teaching-learning-based optimization algorithm embedded with Iterated Greedy (IG).
Iron and steel production is a worldwide problem, which provides raw materials for modern industries, such as machinery manufacturing, shipbuilding. During the production process, Steelmaking-refining-Continuous Casting (SCC) process is the key and bottleneck (Tang et al., 2001, Tang, Wang et al., 2014), which processes hot metal to steel with a well-defined chemical composition and solidifies the steel into slabs (Ribas et al., 2010). The SCC process mainly consists of three stages, i.e. steelmaking, refining, and continuous casting, each of them has multiple parallel machines (Xuan & Tang, 2007). SCC scheduling is usually modeled as a HFS scheduling problem, and thus is NP-hard (Yu, Chai, & Tang, 2016). Moreover, SCC scheduling also has a set of special realistic constraints, such as a pre-defined sequence of charges must be continuously processed on the same machine at the continuous casting stage, which makes that SCC scheduling is more complicated than classical HFS scheduling, and is considered as one of the hardest industrial scheduling problems (Pan, 2016). Effective SCC scheduling methods can help to enhance iron and steel production productivity and increase huge production benefit.
A number of SCC scheduling methods have been proposed (Li et al., 2016, Li et al., 2012, Tang et al., 2001), which mainly can be classified as two categories: mathematical programming and artificial intelligence methods. Among mathematical programming methods, Lagrangian Relaxation (LR) based approaches form a major class, and have received much attention (Cui and Luo, 2017, Mao et al., 2015, Mao et al., 2014a, Tang and Liu, 2007, Tang et al., 2002). With respect to artificial intelligence methods, Pacciarelli and Pranzo (2004) modeled the problem by the alternative graph and presented a beam search approach. Kumar, Kumar, Tiwari, and Chan (2006) designed an auction-based approach. Atighehchian, Bijari, and Tarkesh (2009) presented a hybrid algorithm based on ant colony optimization. Pan, Wang, Mao, Zhao, and Zhang (2013) established a new HFS model for real-world SCC scheduling to minimize the sojourn time and earliness/tardiness of cast starting, and then devised an effective artificial bee colony algorithm. Subsequently, Li, Pan, Mao, and Suganthan (2014) further developed a fruit fly optimization algorithm to solve the same model, achieving better results. Unlike the above research, more recently, Pan (2016) studied SCC scheduling from a new perspective, which decomposed the problem into a parallel machine scheduling for casts in the continuous casting stage and a hybrid flowshop scheduling for charges in the steelmaking and refining stages, and then presented an effective cooperative co-evolutionary artificial bee colony algorithm with two sub-swarms, where each sub-swarm addressed a sub-problem. Based on similar problem decomposition, Jiang, Liu, Hao, and Qian (2015) considered SCC scheduling with controllable processing times and devised a bi-layer optimization approach, where a hybrid DE combined with a variable neighborhood decomposition search acted as the first layer to solve the parallel machine scheduling problem.
However, the above research has not considered unexpected disruptions which always occur in the real-world SCC process, e.g. machine breakdown, job start-time delay, new job arrival, and job cancellation, and thus the research should be called SCC static scheduling. Compared with extensive research on SCC static scheduling, only a few studies have studied SCC rescheduling under dynamic environments, i.e. when disruptions happen, rescheduling the SCC process by repairing the original schedule or regenerating a new optimal schedule. The SCC rescheduling methods in the literature can mainly be classified as three categories: heuristic methods, mathematical programming and artificial intelligence methods. Recently, Yu et al. (2016) developed a heuristic to solve SCC rescheduling with multirefining modes under charge start-time delay disruption. With respect to mathematical programming methods, Mao et al., 2014b, Sun et al., 2017 successively studied SCC rescheduling with machine breakdown and variable processing time, where the efficiency and stability objectives are considered, and further designed effective LR approaches. Regarding artificial intelligence methods, for the above SCC rescheduling problem, Li et al. (2016) devised a hybrid fruit fly optimization algorithm integrated with IG. Tang, Zhao et al. (2014) proposed an improved differential evolution (DE) with real-coded matrix representation, where effective mutation strategy and incremental mechanism were devised. The incremental mechanism generated an initial population for the rescheduling process by utilizing the useful information in the final population of DE for the SCC static scheduling. The above research concentrates on converter breakdown or refining furnace breakdown, while very recently Long, Zheng, and Gao (2017) studied SCC rescheduling with continuous caster breakdown, they formulated a model, and then designed a hybrid genetic algorithm by embedding general variable neighbourhood search. Hao et al., 2015, Jiang et al., 2017 designed simulation-based optimization methods to solve SCC rescheduling with stochastic processing times. Later, they further devised a prediction-based online soft algorithm (Jiang, Liu, Lin, & Zhong, 2016).
Artificial Bee Colony (ABC) algorithm is a powerful swarm intelligence algorithm, which is inspired from collective behavior of social swarms of bees (Karaboga and Akay, 2009, Karaboga et al., 2014). Since being proposed in 2005, the ABC has attracted much research interest (Karaboga et al., 2014, Cui et al., 2017), and has also been successfully applied to solve a varies of difficult combinatorial optimization problems (Hu et al., 2016, Li and Ma, 2017, Li et al., 2016, Ng, Lee, Chan et al., 2017, Ng, Lee, Zhang et al., 2017), such as permutation flowshop scheduling problem (Li and Ma, 2017, Tasgetiren et al., 2013), HFS scheduling problem (Pan, Wang, Li, & Duan, 2014), and flexible job shop scheduling problem (Li et al., 2016, Li et al., 2017). However, to the best of our knowledge, there is little research on designing ABC for the HFS rescheduling, especially the SCC rescheduling.
This paper considers a real-world HFS rescheduling derived from the SCC process of Shanghai Baoshan Iron and Steel Complex in China (Baosteel). The HFS rescheduling considered here are with following specific characteristics: (1) machine breakdown is considered as the disruption; (2) controllable processing times in the continuous casting stage is also considered since processing speed of machines in this stage (called continuous casters) is controllable; (3) a weighted sum of the six realistic objectives is employed to measure the schedule quality, including four efficiency objectives and two system instability objectives, i.e. average sojourn time, earliness of un-started cast starting, tardiness of un-started cast starting, cast-break, amount of operations have been altered in the new schedule, and amount of operations whose starting times have been altered in the new schedule; and (4) the precedence constraints among the jobs at the continuous casting stage are defined in advance. To solve the HFS rescheduling problem, we developed an Improved ABC (IABC), the main contributions are listed as follows: (1) new encoding and decoding strategies are proposed based on the problem characteristics to represent the solutions effectively, where a charge left-shifting strategy is specially designed to decrease the cast break; (2) a population initialization heuristic is devised to generate good search starting-points with a high level of quality and diversity; (3) a variable neighboring operator is proposed to generate high-quality solutions for the employed bee and onlooker bee phases, which achieves a better balance between the exploitation and exploration; (4) a worst solution replacement strategy is developed to enhance the exploitation ability; and (5) comparisons against several state-of-the-art algorithms demonstrate the strength and availability of the IABC.
The rest of this paper is organized as follows. Section 2 describes the HFS rescheduling derived from the SCC rescheduling. In Section 3, the basic ABC is introduced. In Section 4, the proposed IABC is provided. Comparison experiments are given in Section 5. Finally, the conclusion remarks are summarized.
Section snippets
SCC process
A typical SCC process is illustrated in Fig. 1. As shown in Fig. 1, SCC process mainly includes three sequential stages, i.e. steelmaking, refining and continuous casting stages (Cui and Luo, 2017, Pan, 2016). More specifically, the steelmaking stage processes hot molten iron into molten steel by a machine called converter (e.g. LD in Fig. 1), where unrequired impurity ingredients are reduced to certain levels. Subsequently, the refining stage further eliminates the impurities, and also adds
Introduction of the basic ABC
ABC algorithm is a popular swarm intelligence metaheuristic by simulating the intelligent foraging behavior of honeybee swarm (Karaboga et al., 2014). The ABC begins with a randomly generated initial population of food sources (each food source corresponds to a possible solution), and then iteratively performs an evolutionary process of three phases, i.e. employed bee, onlooker bee, and scout bee phases, where the three phases correspond to employed bee, onlooker bee, and scout bee,
The proposed IABC
The basic ABC provides only a general framework, which should be elaborately tailored for solving different combinatorial optimization problems. To solve the SCC rescheduling problem, this section proposes the IABC, which enhances considerably the ABC.
The main design of the IABC is presented in this section. The encoding and decoding approaches are firstly devised, which lay the foundation for the IABC. Then, an initial population heuristic is provided to construct good search starting points.
Computational results
The major concern about using metaheuristics is the quality of the obtained solution. To demonstrate the performance of the IABC, six existing high-quality algorithms in the literature are selected for comparison, including two effective SCC rescheduling algorithms, three effective algorithms published recently for the HFS and regular flowshop problems, and the basic ABC, i.e. (1) Hybrid Fruit fly Optimization Algorithm (HFOA) in Li et al. (2016), (2) Improved Differential Evolution algorithm
Case study
In this section, the IABC is employed to solve a case. In this case, 20 charges are processed sequentially in the steelmaking, refining and continuous casting stage, the corresponding processing times are provided in Table 11. There are three converters, five refining furnaces, and four continuous casters in the shop, where each continuous caster processes a cast. The four casts include 6, 4, 5 and 5 charges, respectively. The transfer times from steelmaking to refining stage and from refining
Conclusions
In this paper, an effective IABC with new encoding and decoding approaches is developed for the SCC rescheduling problem with controllable processing times. In the IABC, we devise a heuristic for population initialization, which can obtain an initial population with certain quality and diversity. Moreover, we design a variable neighboring operator, which can balance the exploration and exploitation abilities of IABC, to generate high-quality neighboring solutions for the employed bee and
Acknowledgments
The authors sincerely thank the editor and anonymous reviewers for their valuable comments and helpful suggestions. This project is supported by the National Natural Science Foundation of China (Grant Nos. 51705177, 51575212, 51775216), and Program for HUST Academic Frontier Youth Team.
References (55)
- et al.
A novel hybrid algorithm for scheduling steel-making continuous casting production
Computers & Operations Research
(2009) - et al.
Flexible flow shop scheduling with stochastic processing times: A decomposition-based approach
Computers & Industrial Engineering
(2012) - et al.
A novel artificial bee colony algorithm with an adaptive population size for numerical function optimization
Information Sciences
(2017) - et al.
An improved Lagrangian relaxation approach to scheduling steelmaking-continuous casting process
Computers & Chemical Engineering
(2017) - et al.
An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion
Computers & Operations Research
(2009) - et al.
A soft-decision based two-layered scheduling approach for uncertain steelmaking-continuous casting process
European Journal of Operational Research
(2015) - et al.
A bi-layer optimization approach for a hybrid flow shop scheduling problem involving controllable processing times in the steelmaking industry
Computers & Industrial Engineering
(2015) - et al.
A prediction-based online soft scheduling algorithm for the real-world steelmaking-continuous casting production
Knowledge-Based Systems
(2016) - et al.
A comparative study of artificial bee colony algorithm
Applied Mathematics and Computation
(2009) - et al.
A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop
Engineering Applications of Artificial Intelligence
(2010)
A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems
Engineering Applications of Artificial Intelligence
Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm
Knowledge-Based Systems
Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems
Computers & Industrial Engineering
A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process
European Journal of Operational Research
An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process
Control Engineering Practice
An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness
Expert Systems with Applications
Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min-max regret approach
Transportation Research Part E: Logistics and Transportation Review
A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion
Computers & Industrial Engineering
Production scheduling in a steelmaking-continuous casting plant
Computers & Chemical Engineering
An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling
European Journal of Operational Research
A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation
Omega
A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems
Computers & Operations Research
Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective
Computers & Operations Research
A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility
European Journal of Operational Research
Modeling realistic hybrid flexible flowshop scheduling problems
Computers & Operations Research
The hybrid flow shop scheduling problem
European Journal of Operational Research
A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex
European Journal of Operational Research
Cited by (81)
A discrete group teaching optimization algorithm for solving many-objective sand casting whole process production scheduling problem
2024, Computers and Operations ResearchProactive scheduling for steel plants with unrelated parallel machines and time uncertainty
2024, Computers and Industrial EngineeringA novel digital twin-assisted prediction approach for optimum rescheduling in high-efficient flexible production workshops
2023, Computers and Industrial EngineeringA Q-learning artificial bee colony for distributed assembly flow shop scheduling with factory eligibility, transportation capacity and setup time
2023, Engineering Applications of Artificial IntelligenceIdentification of heat transfer coefficients in continuous casting by a GPU-based improved comprehensive learning particle swarm optimization algorithm
2023, International Journal of Thermal Sciences