An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem

In this paper, an effective estimation of distribution algorithm (EDA) is proposed to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, the earliest completion factory rule is employed for the permutation based encoding to generate feasible schedules and calculate the schedule objective value. Then, a probability model is built for describing the probability distribution of the solution space, and a mechanism is provided to update the probability model with superior individuals. By sampling the probability model, new individuals can be generated among the promising search region. Moreover, to enhance the local exploitation, some local search operators are designed based on the problem characteristics and utilized for the promising individuals. In addition, the influence of parameter setting of the EDA is investigated based on the Taguchi method of design of experiments, and a suitable parameter setting is suggested. Finally, numerical simulations based on 420 small-sized instances and 720 large-sized instances are carried out. The comparative results with some existing algorithms demonstrate the effectiveness of the proposed EDA in solving the DPFSP. In addition, the new best-known solutions for 17 out of 420 small instances and 589 out of 720 large instances are found. (C) 2013 Elsevier B.V. All rights reserved.