An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling

An entropy-based adaptive estimation of the distribution algorithm (AEDA) is proposed to solve the unrelated parallel machine scheduling problem. According to the characteristic of the problem, a job-machine assignment oriented probabilistic model and its incremental learning based updating method are designed. The learning rate is adjusted with the guidance of the information entropy. To enhance the local exploitation ability, a neighborhood structure based on the critical machine is used for local search. Moreover, the relation between information entropy and learning rate is discussed, and the effect of key parameters on the performance of the algorithm is investigated. Testing results and the comparisons to the existing algorithms by using the benchmark instances demonstrate the effectiveness of both the adaptive adjusting mechanism of the learning rate and the proposed algorithm.