关键词: 组合优化问题, 作业车间调度, 分布估计算法, 一元边缘分布算法, 禁忌搜索算法

Abstract: A Tabu Estimation of Distribution Algorithm（TSEDA） is proposed for the optimization of the job-shop scheduling 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 vector. 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. Computational results demonstrate that the proposed TSEDA algorithm is competitive, and can be rapidly guided.

Key words: combination optimization, job-shop scheduling, Estimation of Distribution Algorithm（EDA）, Univariate Marginal Distribution Algorithm（UMDA）, Tabu Search（TS） algorithm