An Improved Artificial Bee Colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process

https://doi.org/10.1016/j.cie.2018.05.056Get rights and content

Highlights

  • A real-world hybrid flowshop rescheduling problem in SCC process is studied.

  • An Improved ABC (IABC) with new encoding and decoding approaches is developed.

  • A charge left-shifting strategy is proposed in the decoding to decrease cast break.

  • Initialization, variable neighboring operator, worst solution updating are devised.

  • The strength and availability of the IABC is demonstrated by extensive experiments.

Abstract

Realistic production systems usually encounter various of unexpected disruptions, which may invalidate the original schedules, and thus rescheduling becomes essential. This paper studies a real-world hybrid flowshop rescheduling problem in Steelmaking-refining-Continuous Casting (SCC) process, where machine breakdown is considered as the disruption, and controllable processing times in the last stage of SCC process is considered. An Improved Artificial Bee Colony (IABC) algorithm is developed to solve the problem. In the IABC, novel encoding and decoding strategies are devised to represent the solutions effectively, where a charge left-shifting strategy is designed to decrease cast break. A population initialization heuristic is devised to generate solutions with a high level of quality and diversity. Meanwhile, a variable neighboring operator, which can balance the exploration and exploitation abilities, is proposed to generate new solutions with high quality for the employed bee and onlooker bee phases. Moreover, a worst solution replacement strategy is developed to further enhance the exploitation ability. To demonstrate the performance of the IABC, comprehensive computational comparisons against several state-of-the-art algorithms and statistical analysis are conducted, which discloses the strength and availability of the IABC. Moreover, key features of the IABC are analyzed, confirming their critical roles to the success of the IABC.

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)

  • J. Li et al.

    A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems

    Engineering Applications of Artificial Intelligence

    (2015)
  • J. Li et al.

    Solving the steelmaking casting problem using an effective fruit fly optimisation algorithm

    Knowledge-Based Systems

    (2014)
  • X. Li et al.

    Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems

    Computers & Industrial Engineering

    (2017)
  • K. Mao et al.

    A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process

    European Journal of Operational Research

    (2014)
  • K. Mao et al.

    An effective Lagrangian relaxation approach for rescheduling a steelmaking-continuous casting process

    Control Engineering Practice

    (2014)
  • B. Naderi et al.

    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

    (2009)
  • K. Ng et al.

    Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min-max regret approach

    Transportation Research Part E: Logistics and Transportation Review

    (2017)
  • K. Ng et al.

    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

    (2017)
  • D. Pacciarelli et al.

    Production scheduling in a steelmaking-continuous casting plant

    Computers & Chemical Engineering

    (2004)
  • Q. Pan

    An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling

    European Journal of Operational Research

    (2016)
  • Q. Pan et al.

    A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation

    Omega

    (2014)
  • Q. Pan et al.

    A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

    Computers & Operations Research

    (2009)
  • I. Ribas et al.

    Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective

    Computers & Operations Research

    (2010)
  • R. Ruiz et al.

    A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility

    European Journal of Operational Research

    (2006)
  • R. Ruiz et al.

    Modeling realistic hybrid flexible flowshop scheduling problems

    Computers & Operations Research

    (2008)
  • R. Ruiz et al.

    The hybrid flow shop scheduling problem

    European Journal of Operational Research

    (2010)
  • L. Tang et al.

    A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

    European Journal of Operational Research

    (2007)
  • Cited by (81)

    View all citing articles on Scopus
    View full text