求解作业车间调度问题的禁忌分布估计算法

摘要

为优化作业车间调度问题的解,提出一个禁忌和分布估计的混合算法.分布估计算法是一种新的进化模式,通过概率优化模型在连续空间进行求解;通过对已获得的群体进行选择操作生成优势群体,提出的分布估计算法使用单变量边缘分布算法构建概率模型,估计离散空间中的联合概率分布,从概率向量采样生成新群体;采用基于工件编号的编码和解码机制保证解的可行性.为提高局部搜索能力,算法基于禁忌搜索算法设计新的双重移动组合、块禁忌和选择策略,在搜索陷入局部最优时利用遗传算法的变异算子生成新解;算法通过混合分布估计算法和禁忌搜索算法的优点,兼具全局搜索与局部搜索能力,提高了搜索的效率和性能.通过与现有算法在典型实例上的实验结果比较,表明该算法在求解作业车间调度问题上具有可行性和有效性.%A Tabu Estimation of Distribution Algorithm(TSEDA)is proposed for the optimization of the job-shop sched-uling problem. Estimation of Distribution Algorithm(EDA)has presented a new paradigm of evolutionary technique by using novel stochastic optimization strategies to search the solution in a continuous space. Elitist individuals are selected from the obtained groups, Univariate Marginal Distribution Algorithm(UMDA)is used to construct elitist groups and probability model, estimate the union probability distribution, and generate new group by sampling from probability vec-tor. An encoding and decoding mechanism is presented to guarantee the feasibility of the solutions. A new double-moved combined strategy, block tabu strategy and selection strategy are designed to improve local search ability of the Tabu Search(TS)algorithm. A mutation strategy of the genetic algorithm is utilized to generate new solution for jumping out of local optimum. TSEDA hybridizes the EDA and TS for combining the ability of global search and local search and then improving the efficiency and performance of searching. To verify the efficiency and performance of TSEDA algorithm, comparisons are made through using recently proposed algorithm for the problem, addressed in the literature. Computa-tional results demonstrate that the proposed TSEDA algorithm is competitive, and can be rapidly guided.