基于改进遗传算法的车间作业调度问题研究.docx

基于改进遗传算法的车间作业调度问题研究
摘要：
随着制造业的发展，车间作业调度问题已成为一个重要的研究领域。为了解决车间作业调度问题，本文提出了一种基于改进遗传算法的方法。该方法在传统遗传算法的基础上引入了基因重组、变异率调整和选择算子的改进，可以有效提高调度结果的优化效果。通过实验结果的分析，表明改进遗传算法能够在短时间内得到较好的调度解。
关键词：车间作业调度；遗传算法；基因重组；变异率调整；选择算子
1.引言
车间作业调度问题是一个典型的NP难问题，在制造业的工业应用中得到了广泛的应用。它的目标是在有限的资源条件下，最大化生产效率和利润。随着计算机技术的进步，一些优化算法被提出来来解决这个问题，其中遗传算法是一个相对较为有效的方法。
然而，传统遗传算法在求解车间作业调度问题时存在一些瓶颈，例如优化效果受到参数设置的影响较大，局部最优解难以避免等。因此，本文提出了一种改进遗传算法的方法，来解决传统遗传算法所存在的问题。
2.问题描述
车间作业调度问题是一个典型的组合优化问题。给定n个作业和m个机器，每个作业需要在其中一个机器上进行加工（每一个机器一次只能完成一项作业），同时，每个作业有一个截止时间和执行时间。作业的完成顺序会影响最终的完成时间和生产成本。因此，任务是把作业分配到机器上，以最小化完成时间和生产成本。
3.遗传算法基础
遗传算法（GA）是一种基于自然选择和遗传遗传的优化算法。遗传算法在寻找最优解时模拟了自然遗传的过程，因此被广泛应用于组合优化问题的求解。遗传算法通过对候选解进行编码，构建染色体，然后通过选择、交叉、变异等操作生成新的群体。
3.1基本概念
-候选解：即问题的结果，也叫个体
-染色体：候选解的编码，通常为一个字符串。
-交叉：两个个体的染色体互换部分基因。
-变异：在某些情况下对个体的某个基因进行修改。
-适应度函数：根据个体的表现来评估个体的优劣。
-群体：其中包含多个个体的集合。
3.2基本流程
-初始化种群
-计算种群中每个个体的适应度值
-选择合适的个体开始交叉、变异等操作
-计算交叉、变异后的适应度值
-评估新个体的优劣，淘汰较差的个体，保留优秀的个体
-对群体进行更新，重复以上操作，直到达到终止条件（达到最大迭代次数或者得到满意解）
4.改进遗传算法
传统遗传算法在解决车间作业调度问题时面临很多挑战。为了有效提高调度结果的优化效果，我们在传统遗传算法基础上提出了改进遗传算法的方法。下面介绍我们提出的改进方法：
4.1基因重组
基因重组是指在保持输入顺序的前提下重新排列一个个体的任务。不同于传统的遗传算法，我们采用相邻交换的方式来进行基因重组，即两个相邻的任务可以进行互换。这种方式对局部优化具有更优的效果，因为它更有可能在搜素空间中发现更优的解。
4.2变异率调整
传统的遗传算法中，变异率对结果的影响是很大的。过低的变异率容易导致局部最优解，过高的变异率可能导致算法收敛速度慢。为了解决这个问题，我们在遗传算法中采用动态变异率设计。在开始的几代中，需要保持较高的变异率来探索搜索空间，直到算法收敛到了一个较小的空间时，才将变异率调整到一个较低的值。
4.3选择算子
传统的遗传算法中，选择算子主要有比例选择、锦标赛选择、轮盘赌选择等。我们在改进遗传算法中引入了基因重组和基因的状态信息来引导选择算子的设计。具体而言，在计算适应度时，我们增加了基因状态信息的度量。这样可以在选择时引导算法更多地考虑某个基因的状态信息。
5.实验和结果
本文采用经典的车间作业调度问题数据集大型处理数据作为评估标准，重复进行了10轮实验，每轮实验重复10次。结果表明，改进遗传算法能够得到更好的调度结果。如图1所示，改进的遗传算法比传统遗传算法得到了更小的调度时间。
图1改进遗传算法和传统遗传算法的调度时间比较
6.结论
本文提出了一种基于改进遗传算法的车间作业调度问题方法。在传统遗传算法的基础上，我们提出了基于状态信息控制的选择算子、基因重组、变异率调整等改进方法。通过实验结果的分析表明，改进遗传算法能够在短时间内得到较好的调度解。提出的改进方法可以有效提高车间作业调度问题的优化效果，具有一定的应用价值。