遗传算法在机械制造车间调度里面的应用研究

摘要

机械制造车间调度是调度问题的一个重要内容，它指的是在生产过程里面促进共同使用的资源通过时间分配来达到某一最优效果。在调度问题里面，有许多优化决策问题，机械制造车间调度作为制造型企业不可或缺的环节之一，通过采用合理的机械制造车间调度方案促进提高企业的生产效率具有重要意义，不光能高效地减少设备的空置率，缩短产品生产的周期，而且还能减少生产成本和提高经济效益。根据机械制造车间调度里面工件的工艺路线，机械制造车间调度有作业机械制造车间调度和流水机械制造车间调度之分。在众多的制造型企业里面，往往具有无数的生产机械制造车间，之所以，促进机械制造车间优化调度配置问题的研究具有重要意义。

同时机械制造车间调度问题作为一个NP(Non．deterministic Polynomial多项式复杂程度的非确定性问题)难题，随着需要加工的工件数和机器数量的提高，可选调度方案数量将以指数速度急剧增长。之所以，用遗传算法求解该问题就成为人们研究的一个重要方向。本文将在建立机械制造车间调度问题数学模型的基础上，研究采用遗传算法促进其求解。

本文围绕基于最大完成时间为目标的机械制造车间调度问题开展研究，主要做了以下工作：

(1)本文分析了作业机械制造车间调度问题的数学模型，并在此基础上促进作业机械制造车间调度问题的特例流水机械制造车间调度问题也建立了数学模型；

(2)本文采用遗传算法来解决机械制造车间优化调度问题，同时针促进作业机械制造车间和流水机械制造车间两种调度问题分别给出了采用遗传算法解决机械制造车间优化调度问题的算法模型和实现过程；

(3)促进遗传算法的优化特性进行了分析，并在SGA(Simple 

GeneticAlgorithms，基本遗传算法)的基础上促进遗传算法进行了一定的改进；

(4)促进本文提出的解决方法进行了试验计算，并分析了基本遗传算法和

改进后遗传算法各自的特点。

关键词：作业机械制造车间调度，流水机械制造车间调度，遗传算法，优化问题

第一章 绪  论

1.1选题背景和意义

在当代经济环境下，市场的发展与变化促使了传统生产方式的变革，制造业面临着巨大的压力，以较低的生产成本和较短的生产周期开发更多的新产品才能满足激烈的市场竞争需要。与此同时，随着科学技术的发展，生产规模越来越大，复杂程度越来越高，促进企业管理和生产过程的合理安排有了更高的要求。机械制造车间作为生产过程的最基本单元，机械制造车间调度利用已有的资源，通过实现满足某种约束条件(如加工工序、所需机器等)来达到某一最优效果。

机械制造车间调度是制造系统的一个研究热点，他不光是一个典型的NP难题，也是至今为止所有组合优化问题里面最难问题之一，所以得到了广泛的关注。机械制造车间调度是生产管理的核心内容和关键技术，科学制定机械制造车间调度方案促进提高企业的生产效率具有重要意义，不光能够高效地减少设备的空置率，缩短产品生产周期，而且还能减少生产成本和提高经济效益。

早在20世纪50年代初就有很多关于调度问题的研究文献。在计算机出现以前，作业机械制造车间调度问题(Job Shop Scheduling Problem，简称为JSP)是用手工计算完成的。但是由于问题本身复杂、计算量大、手工操作可靠性差、调度方案优化性能不好，跟不上产品的多变性要求又容易受随机因素的干扰，使资源和生产能力得不到充分的发挥和利用，机械制造车间生产效率不高。

随着计算机信息技术的发展，机械制造车间调度问题也没有得到很好的解决，因为问题的规模和实时性要求也在不断提高。现在大多数学者和研究人员把研究重点放到了“近似方法”上，如随机局部搜索方法。尤其是促进于大规模的问题，在有限的时间内找到一个可以接受的近似最优解成为当前调度问题研究的一个焦点。

1.2机械制造车间调度问题研究进展