A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion

• A novel bi-population EDA for NIFPSP.
• Suitable adjusting mechanisms for adjusting probability models.
• Insertion based local search procedure to enhance exploitation.
• Better results obtained than those by the existing meta-heuristics.

In this paper, an effective bi-population estimation of distribution algorithm (BEDA) is presented to solve the no-idle permutation flow-shop scheduling problem (NIPFSP) with the total tardiness criterion. To enhance the search efficiency and maintain the diversity of the whole population, two sub-populations are used in the BEDA. The two sub-populations are generated by sampling the probability models that are updated differently for the global exploration and the local exploitation, respectively. Meanwhile, the two sub-populations collaborate with each other to share search information for adjusting the models. To well adjust the models for generating promising solutions, the global probability model is updated during the evolution with the superior population and the local probability model is updated with the best solution that has been explored. To further enhance exploitation in the promising region, the insertion operator is used iteratively as the local search procedure. To investigate the influence of parameter setting, numerical study based on the Taguchi method of design-of-experiment is carried out. The effectiveness of the bi-population strategy and local search procedure is shown by numerical comparisons, and the comparisons with the recently published algorithms by using the benchmarking instances also demonstrate the effectiveness of the proposed BEDA.