Paper Info
Title
Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion.
Abstract
Display Omitted A hybrid node and edge histogram matrix (NEHM) is constructed.A random sample crossover with NEHM is proposed.An improved general variable neighborhood search with the simulated annealing acceptance is presented.89 new best solutions for the benchmark of Ruiz are provided. This paper presents a memetic algorithm with hybrid node and edge histogram (MANEH) to solve no-idle permutation flow shop scheduling problem (NIPFSP) with the criterion to minimize the maximum completion time (the makespan criterion). The MANEH mainly composes of two components: population-based global search and local refinements for individuals. At the initialization stage, a modified speed-up NEH method and the random initialization are utilized to generate more promising solutions with a reasonable running time. At the population-based global search stage, a random sample crossover is first proposed to construct a hybrid node and edge histogram matrix (NEHM) with superior solutions in the population, and then a new sequence is generated by sampling the NEHM or selecting jobs from a template sequence. At the local refinements stage, an improved general variable neighborhood search with the simulated annealing acceptance (GVNS-SA) is developed to improve the current best individual. The GVNS-SA adopts a random referenced local search in the inner loop and the probability of SA to decide whether accept the incumbent solution for the next iteration. Moreover, the influence of key parameters in the MANEH is investigated based on the approach of a design of experiments (DOE). Finally, numerical simulation based on the benchmark of Ruiz and thorough statistical analysis are provided. The comparisons between MANEH and some existing algorithms as well as MA-based algorithms demonstrate the effectiveness and superiority of the proposed MANEH in solving the NIPFSP. Furthermore, the MANEH improves 89 out of the 250 current best solutions reported in the literature.
Year
DOI
Venue
2017
10.1016/j.asoc.2017.01.017
Appl. Soft Comput.
Keywords
Field
DocType
Memetic algorithm,Node and edge histogram,Random sample crossover,Local refinements,No-idle permutation flow shop scheduling problem
Simulated annealing,Memetic algorithm,Histogram,Mathematical optimization,Job shop scheduling,Crossover,Variable neighborhood search,Flow shop scheduling,Artificial intelligence,Local search (optimization),Mathematics,Machine learning
Journal
Volume
Issue
ISSN
54
C
1568-4946
Citations 
PageRank 
References 
11
0.57
19
Authors
3
Name
Order
Citations
PageRank
Weishi Shao1705.06
De-Chang Pi217739.40
Zhongshi Shao3927.91