A hybrid discrete optimization algorithm based on teaching–probabilistic learning mechanism for no-wait flow shop scheduling

作者:

Highlights:

摘要

Inspired by the phenomenon of teaching and learning introduced by the teaching-learning based optimization (TLBO) algorithm, this paper presents a hybrid discrete optimization algorithm based on teaching-probabilistic learning mechanism (HDTPL) to solve the no-wait flow shop scheduling (NWFSSP) with minimization of makespan. The HDTPL consists of four components, i.e. discrete teaching phase, discrete probabilistic learning phase, population reconstruction, neighborhood search. In the discrete teaching phase, Forward-insert and Backward-insert are adopted to imitate the teaching process. In the discrete probabilistic learning phase, an effective probabilistic model is established with consideration of both job orders in the sequence and similar job blocks of selected superior learners, and then each learner interacts with the probabilistic model by using the crossover operator to learn knowledge. The population reconstruction re-initializes the population every several generations to escape from a local optimum. Furthermore, three types of neighborhood search structures based on the speed-up methods, i.e. Referenced-insert-search, Insert-search and Swap-search, are designed to improve the quality of the current learner and the global best learner. Moreover, the main parameters of HDTPL are investigated by the Taguchi method to find appropriate values. The effectiveness of HDTPL components is analyzed by numerical comparisons, and the comparisons with some efficient algorithms demonstrate the effectiveness and robustness of the proposed HDTPL in solving the NWFSSP.

论文关键词:Discrete teaching,Discrete probabilistic learning,Population reconstruction,Neighborhood search,No-wait flow shop scheduling,Minimization of makespan

论文评审过程:Received 24 January 2016, Revised 22 May 2016, Accepted 10 June 2016, Available online 11 June 2016, Version of Record 9 July 2016.

论文官网地址:https://doi.org/10.1016/j.knosys.2016.06.011