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

发布时间：2018-03-01 01:26

本文关键词： 组合优化问题作业车间调度分布估计算法一元边缘分布算法禁忌搜索算法　出处：《计算机工程与应用》2017年07期 　论文类型：期刊论文

【摘要】：为优化作业车间调度问题的解,提出一个禁忌和分布估计的混合算法。分布估计算法是一种新的进化模式,通过概率优化模型在连续空间进行求解;通过对已获得的群体进行选择操作生成优势群体,提出的分布估计算法使用单变量边缘分布算法构建概率模型,估计离散空间中的联合概率分布,从概率向量采样生成新群体;采用基于工件编号的编码和解码机制保证解的可行性。为提高局部搜索能力,算法基于禁忌搜索算法设计新的双重移动组合、块禁忌和选择策略,在搜索陷入局部最优时利用遗传算法的变异算子生成新解;算法通过混合分布估计算法和禁忌搜索算法的优点,兼具全局搜索与局部搜索能力,提高了搜索的效率和性能。通过与现有算法在典型实例上的实验结果比较,表明该算法在求解作业车间调度问题上具有可行性和有效性。
[Abstract]:In order to optimize the solution of job shop scheduling problem, a hybrid algorithm of Tabu and distribution estimation is proposed, which is a new evolutionary model and is solved in continuous space by probabilistic optimization model. The distribution estimation algorithm uses the single variable edge distribution algorithm to construct the probability model, estimates the joint probability distribution in the discrete space, and generates the new population from the probability vector sampling. In order to improve the local search ability, the algorithm based on Tabu search algorithm designed a new dual moving combination, block taboo and selection strategy. When the search falls into the local optimum, the mutation operator of the genetic algorithm is used to generate the new solution, the algorithm has the advantages of the hybrid distribution estimation algorithm and the Tabu search algorithm, and has both global and local search capabilities. The efficiency and performance of search are improved. Compared with the experimental results of typical examples, the proposed algorithm is feasible and effective in solving job shop scheduling problems.
【作者单位】：云南大学软件学院;
【基金】：国家自然科学基金(No.61462095) 云南大学中青年骨干教师培养计划项目(No.XT412003) 云南省软件工程重点实验室面上基金(No.2012SE301)
【分类号】：TP18;TB497

【相似文献】