基于遗传算法的车间生产调度问题研究

《基于遗传算法的车间生产调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文摘要随着客户需求日趋多样化，产品的生产技术在不断更新，各行业间的竞争逐渐加剧，每一个企业都面临着生存危机，为了占领市场，他们必须以低成本、快速度开发出高质量的新产品。因此企业都迫切需要寻求一种新的生产方式来缩短产品开发周期，降低生产成本，最终实现效益最大化。作为企业生产管理中一个必不可少的环节，车间生产调度管理是生产管理任务顺利实施和完成的重要保障。目前对于车间生产调度问题的研究主要集中在如何合理的配置加工过程的各种资源，减少工件加工准备、等待时间。因此对这一问题的研究具有广阔的应用前景。作业车间调度问题是车间生产调度中的一个典型问题，它是在满足一定约束

2、条件下，研究对各道工序加工顺序的排列以使相应的性能指标达到最优。根据约束条件的不同，作业车间调度问题可分为经典作业车间调度问题和柔性作业车间调度问题两类。研究表明，随着问题规模的扩大，求解作业车间调度问题的复杂度会呈指数增长。由于遗传算法具有隐含并行性和全局优化的特点，它已经成为目前求解作业车间调度问题的有效方法之一。但该算法所存在的早熟收敛和局部搜索能力较差的缺点却制约了它在这一领域的深入研究。为了提高遗传算法求解作业车间调度问题的效率，本文结合逆序数、信息熵和协同进化等理论，提出了一系列遗传调度算法,主要取得了如下的研究成果:(1)基于随机性指导策略的作

3、业车间遗传调度算法由于遗传算法在操作中具有随机性操作，这些操作使算法的执行结果具有不确定性，为了提高算法求解结果的稳定性，有效指导算法的进化方向，针对经典作业车间调度问题，提出了一类基于随机性指导策略的遗传调度算法。这类算法包括基于信息熵的遗传调度算法和基于逆序数的遗传调度算法。其中，基于信息熵的遗传调度算法是借助生态学的多样性指数和决策树算法的属性选择准则所提出的。该算法利用信息熵值的差异确定参与复制的个体，在交叉和变异算子的设计中引入信息熵衡量工序、机器的重要度，并利用交叉父代表示的调度方案所隐含的信息获取优良基因排列。其次，通过分析求解作业车间调度问题

4、和旅行商问题所采用的遗传算子，提出了基于逆序数的遗传调度算法。该算法在遗传过程中利用相对逆序数检验群体的一致性，并根据排列奇偶性的改变进行交叉(或变异)操作，从而产生后代群体。实验结果验证了所提出的遗传调度算法的有效性。(2)基于协同进化的作业车间遗传调度算法为了增强遗传算法的并行处理能力，针对经典作业车间调度问题，提出了一类基于协同进化的遗传调度算法。该算法包括基于群体间协同进化的遗传调度算法和基于个体间协同进化的遗传调度算法。其中，基于群体间协同进化的遗传调度算法借鉴标准协同进化遗传算法的性质，在操作中结合子种群共同进化的原则，并利用基于排名的选择方法，

5、从多种遗传算子中选择出相应的交叉(或变异)方法而产生遗传后代。基于个体间协同进化的遗传调度算法则是利用多个个体参与遗传算子的操作，借助个体间调度解和染色体结构的区别指导交叉(或变异)父代的产生。这类算法从群体和个体间的进化过程、遗传操作中的选择策略(父代的选择、算子的选择)等方面真正体现出了算法并行处理的特征。实验结果表明，基于协同进化的遗传算法能够有效求解经典作业车间调度问题。(3)改进的柔性作业车间遗传调度算法通过对目前柔性作业车间调度算法的分析，针对具有不同目标的柔性作业车间调度问题，提出了两种改进的遗传调度算法。首先，针对单目标柔性作业车间调度问题，

6、提出了一种分部遗传调度算法。该算法将分部编码方法和分部遗传算子操作有效地加以结合，由此能够直接产生可行的调度方案；其次，针对多目标柔性作业车间调度问题提出了一种改进的遗传算法。该算法首先利用矩阵编码方法缩小了求解空间，并从符合各项约束条件出发，对解码步骤进行详细阐述，从而保证算法能够产生可行的调度方案。然后借助根据选择机制和木桶原理设计的遗传调度算子的操作产生可行的遗传后代。实验结果验证了所提出算法求解柔性作业车间调度问题的有效性和可行性。(4)基于基尼指数的遗传调度算法通过对不同类型作业车间调度问题的分析，提取各问题间的共性部分，并借鉴进化生态学原理和决策

7、树算法的属性分裂准则，提出了一种基于基尼指数的遗传调度算法。该算法针对经典作业车间调度问题和柔性作业车间调度问题，挖掘出各问题间的共性特征，对其相同的特性采用基于基尼指数的遗传算子操作，同时采用基尼指数作为个体多样性和优劣性的衡量指标，通过和目前其它调度算法的实验结果的比较，证实了所提出的算法对于具有共性特征的作业车间调度问题的求解是非常有效的。总之，本文针对经典作业车间调度问题、柔性作业车间调度问题及具有共性特征的车间调度问题提出了一系列遗传调度算法，这些算法的提出不仅适用于求解制造业的各类车间调度问题，还为遗传算法在物流业、交通业、服务业等领域进行车辆调

8、度、人员优化配置的研究拓展了思路。关键词：生产管理；