计算机工程与应用2017，Vol.53Issue(7)：147-153,7.DOI:10.3778/j.issn.1002-8331.1510-0004
求解作业车间调度问题的禁忌分布估计算法
Tabu estimation of distribution algorithm for job-shop scheduling problem
摘要
Abstract
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.关键词
组合优化问题/作业车间调度/分布估计算法/一元边缘分布算法/禁忌搜索算法Key words
combination optimization/job-shop scheduling/Estimation of Distribution Algorithm(EDA)/Univariate Marginal Distribution Algorithm(UMDA)/Tabu Search(TS)algorithm分类
信息技术与安全科学引用本文复制引用
杨小东,康雁,柳青,孙金文..求解作业车间调度问题的禁忌分布估计算法[J].计算机工程与应用,2017,53(7):147-153,7.基金项目
国家自然科学基金(No.61462095) （No.61462095）
云南大学中青年骨干教师培养计划项目(No.XT412003) （No.XT412003）
云南省软件工程重点实验室面上基金(No.2012SE301). （No.2012SE301）
