一种基于新型混合分布估计算法求解流水车间调度问题
目前我国已经成为制造业大国,是世界的制造中心,但是我国的制造业与西方发达国家相比并不成熟,存在很多弊端,例如资源浪费,工人工作时间过长,生产效率低下等等.如何提高生产效率、合理配置资源越来越引起了人们的重视,车间调度问题作为制造系统的研究热点受到了广泛的关注,并取得了较大的进展.流水车间调度问题是典型的NP难题,是车间调度问题中最为常见的问题,在制造业中大量存在,关于流水车间调度问题的研究有着较高的理论价值和实际意义.本文采用一种新型的混合分布估计算法求解了流水车间调度问题中的置换流水车间调度问题和无等待的流水车间调度问题.分布估计算法由遗传算法发展而来,并被广泛应用于NP难题的研究.其摒弃了遗传算法中复杂的交叉、变异等操作,取而代之的是构造一个表示解分布的概率模型,然后利用一定策略根据概率模型产生新一代的种群.本文针对流水车间调度问题的特点,提出了一种基于工件加工位置概率与连接概率相结合的混合分布估计算法,该算法将工件位置概率与连接概率结合在一起,作为新一代种群的生成概率从而使得进化趋势更加合理化.算法引入了启发式方法提高初始解质量,并引入邻域搜索策略与2-opt操作,从而提高了算法的局部搜索能力.同时引入了变异操作及限定操作用来提高算法全局搜索能力,实验结果表明算法在求解置换流水车间调度问题时具有良好的性能.
- 作者:
- 马云永
- 学位授予单位:
- 辽宁科技大学
- 专业名称:
- 智能算法调度
- 授予学位:
- 硕士
- 学位年度:
- 2015年
- 导师姓名:
- 张晓霞
- 中图分类号:
- TB497
- 关键词:
- 分布估计算法;流水车间调度问题;邻域搜索;位置概率;连接概率
- Estimation of distribution algorithms; Flow-shop scheduling problem; Neighborhood search; Position probability; Connection probability