A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem

In this paper, an effective bi-population based estimation of distribution algorithm (BEDA) is proposed to solve the flexible job-shop scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). The BEDA stresses the balance between global exploration and local exploitation. In the framework of estimation of distribution algorithm, two sub-populations are used to adjust the machine assignment and operation sequence respectively with a splitting criterion and a combination criterion. At the initialization stage, multiple strategies are utilized in a combination way to generate the initial solutions. At the global exploration phase, a probability model is built with the superior population to generate the new individuals and a mechanism is proposed to update the probability model. At the local exploitation phase, different operators are well designed for the two sub-populations to generate neighbor individuals and a local search strategy based on critical path is proposed to enhance the exploitation ability. In addition, the influence of parameters is investigated based on Taguchi method of design of experiment, and a suitable parameter setting is determined. Finally, numerical simulation based on some widely used benchmark instances is carried out. The comparisons between BEDA and some existing algorithms as well as the single-population based EDA demonstrate the effectiveness of the proposed BEDA in solving the FJSP. (C) 2011 Elsevier Ltd. All rights reserved.