APP下载

改进遗传算法求解柔性作业车间调度问题

2017-05-10邹泽桦曾九孙蔡晋辉

计算机测量与控制 2017年4期

邹泽桦,曾九孙,蔡晋辉

(中国计量大学 计量测试工程学院,杭州 310000)

改进遗传算法求解柔性作业车间调度问题

邹泽桦,曾九孙,蔡晋辉

(中国计量大学 计量测试工程学院,杭州 310000)

针对柔性作业车间调度问题中最大完工时间、机器最大负荷和总机器负荷三项性能指标,提出一种改进的自适应交叉和变异的混合遗传算法;在基本遗传算法染色体编码的基础上,设计一种基于海明距离的调度个体差异判别方法,并通过自适应交叉阈值和动态变异概率计算提高遗传算法整个种群调度个体的多样性,防止算法过早的进入早熟;在遗传算法进化期间,对每个调度个体的进化采用变邻域搜索算法,扩大调度个体的邻域搜索范围;最后,使用文献中相同的调度实例将文章的计算结果与其它文献中的测试结果进行比较,验证了所提出的算法的可行性和有效性。

柔性作业车间调度; 海明距离; 遗传算法; 变邻域搜索算法

0 引言

柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)是传统作业车间调度问题(job-shop scheduling problem,JSP)的扩展,由Bruker和Schile[1]于1990年首次提出。目前,对柔性作业车间调度问题的算法研究比较普遍。如Liao等[2]采用禁忌搜索法;Birgin等[3]采用列表排程和集束搜索相结合的方法;安玉伟[4]设计了一种基于拉格朗日松弛的分解方法,在确定计划问题后再对调度问题求解;黄敏[5]等在考虑设备带有恶性条件的情况下使用嵌套分割算法与单亲遗传算法相结合的方法。同时,将排程算法应用到工厂的实例也越来越多,郑克波[6]通过遗传算法实现对某轴承企业的生产排程;……

登录APP查看全文