求解不相关并行机调度的一种自适应分布估计算法

针对不相关并行机调度问题, 提出一种基于信息熵的自适应分布估计算法. 根据问题特性, 设计了面向工件机器分配的概率模型及其基于增量学习的更新方式, 学习速率基于信息熵进行调整. 为了增强算法局部寻优能力, 采用基于关键机器的邻域结构进行局部搜索; 同时讨论了信息熵与学习速率的关系, 并探讨了关键参数对算法性能的影响. 基于标准算例的测试结果与算法比较, 验证了学习速率的自适应调整机制以及所提出算法的有效性.

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.