4.7 Article

A multi-start variable neighbourhood descent algorithm for hybrid flowshop rescheduling

Journal

SWARM AND EVOLUTIONARY COMPUTATION
Volume 45, Issue -, Pages 92-112

Publisher

ELSEVIER
DOI: 10.1016/j.swevo.2019.01.002

Keywords

Hybrid flowshop rescheduling; Dynamic events; Combinatorial optimization; Variable neighbourhood descent; Restart

Funding

  1. National Natural Science Foundation of China [51705177, 51575212, 51825502, 51775216]
  2. Natural Science Foundation of Hubei Province [2018CFA078]
  3. Program for HUST Academic Frontier Youth Team

Ask authors/readers for more resources

Hybrid flowshop (HFS) rescheduling has important applications in modern industry. Much of the existing research on HFS rescheduling only consider one type of dynamic event. However, realistic production systems often encounter several types of dynamic events. In this paper, HFS rescheduling considering simultaneously three types of dynamic events (i.e. machine breakdown, new job arrival and job release variation) is studied. The mathematical model of minimizing makespan and system instability is established. The approaches for calculating lower and upper bounds of the two optimization objectives are developed. A Multi-Start Variable Neighbourhood Descent (MSVND) algorithm is proposed for the HFS rescheduling. In the MSVND, a hybrid decoding is developed. To improve the intensification of the MSVND, a Fruit Fly Optimization (FFO)-based local search and an enhanced FFO-based local search are designed to improve the best solution found so far. Moreover, to enhance the diversification, a simulated annealing-like acceptance criterion is employed to determine whether the local optima can be accepted, and a restart strategy with perturbation is devised to guide the search to the so far unexplored area. Extensive experimental comparisons on 150 instances verify the effectiveness of the devised strategies. Further, a comprehensive comparison against seven highly efficient algorithms demonstrates the superiority of the MSVND.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available