求解柔性作业车间调度问题的混合分布估计算法  

An Hybrid Estimation of Distribution Algorithm for Solving Flexible Job-Shop Scheduling Problem

作　　者：张玺[1] 刘明周[1] 

机构地区：[1]合肥工业大学机械工程学院,合肥230009

出　　处：《系统科学与数学》2017年第1期89-99,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家重点基础研究发展计划(973计划)(2011CB013406);国家自然科学基金(51375134)资助课题

摘　　要：针对柔性作业车间调度问题,提出了一种有效的混合分布估计算法.算法采用基于排序的编码和解码方法.为了保持种群多样性,采用k-均值聚类方法对种群进行分簇,从各子簇中选取具有代表性的若干个体组成优势种群以建立描述问题解空间分布的概率模型,该优势种群包含了全局统计信息及个体特征信息,利用变邻域搜技术优化种群中的最佳个体,避免其陷入局部最优.最后,通过算例仿真,表明算法具有良好的全局搜索能力和局部求精能力.An effective hybrid estimation of distribution algorithm （EDA） was pro- posed to solving flexible job-shop scheduling problem. The permutation based en- coding and decoding schemes were applied. In order to maintain the diversity of population, k-means clustering was used here to classify the population. Purther- more, the superior population was constituted by the typical individuals from each sub-cluster. Then the superior population and individual characteristic information. contains the global statistical information The variable neighborhood search （VNS） was imported to EDA and optimized the best individuals in the population, avoiding premature convergence and trapping in the local optimum. Finally, comparing with some other existing algorithms, numerical simulation was carried out based on some instances to demonstrate the effectiveness and robustness of the proposed algorithm.

关 键 词：分布估计算法 变邻域搜索 K-均值聚类 柔性作业车间调度 

分 类 号：TB497[一般工业技术]