《基于遗传算法的生产调度》由会员分享，可在线阅读，更多相关《基于遗传算法的生产调度（31页珍藏版）》请在金锄头文库上搜索。
1、摘 要 作业车间调度问题(Job-shop Scheduling Problem, 简称JSP)是一类满足任务配置和顺序约束要求的资源分配问题，是一类典型的NP-hard问题，至今没有找到可以精确求得最优解的多项式时间算法。有效地调度方法和优化技术的研究与应用，对于制造企业提供生产效率、降低生产成本有着重要的作用，因此越来越受学者们的关注。遗传算法是基于“适者生存”的一种高度并行、随机和自适应优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。本文系统介绍了作业车间调
2、度问题以及遗传算法的基本原理，并针对作业车间调度问题的特点，设计了一种遗传算法。最后使用Matlab编写程序求解Job Shop调度问题。并对两类典型的FT类问题FT06和FT10进行测试。关键词：车间调度，遗传算法，Job Shop问题Abstract Job shop scheduling problem (Job-shop Scheduling Problem, referred to as JSP) is a class of constraints to meet the tasks required to configure and order the allocation of
3、resources.It is a kind of typical NP-hard problem, which has not found the optimal solution to get accurately obtained polynomial time algorithm. Effective methods and optimization techniques in scheduling research and applications, take an important role in manufactur enterprises production efficie
4、ncy, reduce production costs, so more and more attention by scholars. Genetic algorithm is based on the survival of the fittest in a highly parallel, random and adaptive optimization algorithm, it will solve the problem that a chromosome of the survival of the fittest process, through chromosome gro
5、up of evolving from generation to generation, including reproduction, crossover and mutation operations, and eventually converge to the best adapt to the environment, the individual, and thus obtain the optimal solution or a satisfactory solution. This paper introduced the job-shop scheduling proble
6、m and the basic principles of genetic algorithms, to sove job shop scheduling problem, we designed a genetic algorithm, and using Matlab programming sove Job Shop Scheduling Problem. Finally test two typical kinds of problems FT06 and FT10.Keyword: Production scheduling, Genetic algorithm, Job Shop
7、problemI目录目 录摘 要IAbstractII第一章 绪论11.1车间调度研究的目的和意义11.2 车间调度的研究现状21.3 本文安排3第二章 车间调度问题综述42.1 车间调度问题42.1.1 车间调度问题的描述42.1.2 车间调度的性能指标42.1.3 车间调度问题的分类52.1.4 实际调度问题的特点52.2 车间调度问题的研究方法62.3 车间调度研究中存在的主要问题92.4 本章小结9第三章 遗传算法理论综述103.1 遗传算法的形成和发展103.2 基本遗传算法113.3 基本遗传算的实现技术133.3.1 编码方法133.3.2 适应度函数的确定143.3.3 选择算
8、子143.3.4 交叉算子153.3.5 变异算子153.3.6 算法参数的选取163.3.7 算法终止条件的确定163.4 遗传算法的应用173.5 本章小结17第四章 Job Shop调度问题的遗传算法研究184.1 Job Shop调度问题描述184.2 Job Shop调度的参数设计194.2.1 基本流程图204.2.2 编码方式的确定204.2.3 适应度函数214.2.4 遗传算子的设计214.2.5算法参数的设计224.3 Job Shop调度的Matlab实现224.4 本章小结24第五章 结论与展望255.1 结论255.2 展望25参考文献27致谢28参考文献第一章 绪论
9、本文的主要内容是运用遗传算法解决车间调度中的作业车间调度（Job Shop）问题。因此，本章首先介绍车间调度研究的目的和意义以及车间调度目前的研究现状，最后简单介绍本文的安排。1.1车间调度研究的目的和意义为了适应激烈的市场竞争，多元化、多品种、小批量、高柔性生产方式正逐渐成为主流，生产的复杂性也越来越高，这对企业的管理和对生产过程的监控都提出了更高的要求。为了保证生产的高效稳定运行，以获得最大的经济效益，原来简单、局部和常规的生产计划及仅凭经验的管理已经不能满足现代生产的要求了。企业管理者面临的问题是：如何根据市场上原材料供应和产品需求的变化进行经营决策和组织生产；如何在生产计划改变的情况下
10、对生产过程进行控制，以便最大限度地发挥生产的柔性；如何在生产工艺不做大的改变前提下进行管理、决策，使企业生产最大的综合经济效益。有限资源的合理配置与优化利用问题一直是人类社会所面临的最基本经济学问题，从一个国家、社会的宏观经济运行到企业的微观经济活动，都要受到资源条件的制约。这个问题涉及到了国民经济从宏观到微观的各个方面，人们对他的研究也就从不同的角度进行，产生了有关这类问题的不同的学科和理论，其中在生产邻域产生了重要的车间调度理论。车间调度理论源于对制造车间生产计划与控制的研究，从诞生之日起它就引起了运筹学专业人员、管理科学家和应用数学家等的重视，人们在这个领域出版和发表了大量的文献著作，还
11、有一些学者从不同的广度和深度考察了调度理论的发展状况。经过几十年的研究与探索，调度理论逐渐发展成为一个比较完整的科学理论，在企业的生产中得到了一定程度的应用，而且其研究范围已经从制造业的车间扩展到了物流、能源、交通运输和社会服务等许多行业和研究领域。作为一个关键模块，车间调度是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化和计算机技术发展的中心，在工厂经营管理、产品制造这两个层次上都占有极其重要的地位和作用。车间调度主要用于解决工件在机器上的调度和资源分配问题，可以大大提高生产效率和资源利用率，进而增加企业的竞争力。因此对制造企业车间作业调度问题进行研究与有重要的现实意义，它是实
12、现车间作业调度的合理化、自动化和集成化重要环节。然而，目前在我国许多国有大中型企业生产管理技术及手段落后，缺乏系统科学的车间调度方法，生产计划和调度安排仍然依靠经验，导致产品制造周期长，资源有效利用率低，制造成本偏高，交货期长，对市场反映不够灵敏，严重影响了企业的经济效益，甚至造成许多企业亏损。为了改变这种状况，一些企业从国外引进了一些较为先进的生产管理技术和信息系统，如MRP（制造资源计划）技术和看板控制方法等，它们在一定范围内得到了应用，但都存在局限性，比如MRP更多的是强调对整个企业生产计划的编制，对车间层的生产控制能力不足，特别是对生产能力的估计脱离实际，对车间生产环境变化的适应性不强
13、，看板控制方法的应用也需要较为特殊的条件，而且国外的东西并不能都适用于国内，所以大多数制造企业的车间生产计划和调度还处在依赖车间管理人员工作经验的安排阶段。1.2 车间调度的研究现状调度问题的研究始于20世纪50年代，Johnson提出了解决车间调度部分特殊问题的优化算法，代表调度理论研究的开始。60-70年代建立了调度理论的主体（经典调度理论）并重视调度复杂性的研究。大量的研究促使车间调度领域取得了丰硕的成果，产生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法。Davis1是最早把遗传算法（GA）应用于车间调度问题的学者之一
14、，他在使用GA求解车间调度的研究中取得了近似最优解。1985年，Davis发表了关于把GA成功应用于车间调度问题的论文，充分展示了GA在解决车间调度问题中的前景。此后，很多学者就遗传算法在车间调度问题方面的应用作了大量研究，发表了大量卓有成效的论文，是车间调度这类NP-hard问题的解决展露曙光。国内对车间调度的研究起步较晚，由于技术上的制约，基本上是依靠调度人员的经验进行车间分配和调度。随着各种智能算法尤其是遗传算法在作业调度方面的应用，国内掀起了一股应用遗传算法研究车间调度的热潮：研究工作主要集中在清华大学的CIMS2国家重点实验室，而目前这些实验室的系统开发基本上还处在刚投入试运行阶段，
15、距离开发出成熟的软件系统还有很长距离，实验室还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业调度算法的研究方面。1.3 本文安排本文研究的框架如图所示：图1-1 本文框架图本论文共分为5章，各章内容如下：第1章 绪论。简要介绍了本课题的目的及意义和车间调度目前的研究现状，并阐述了论文的安排。第2章 车间调度问题综述。详细介绍了车间调度问题的分类、特点、研究背景，以及主要的研究方法和存在的问题。第3章 遗传算法的基本原理。详细介绍了遗传算法的形成、发展、特点以及遗传算法的实现技术和应用领域，为第四章编程解决Job Shop调度问题提供理论基础。第4章 Job Shop问题的遗传算法研究。详细介绍了典型的Job Shop调度的描述和求解方法，然后对遗传算法参数进行设计，最后对两类典型的FT类问题FT06和FT10进行测试。第5章 结论与展望。第二章 车间调度问题综述2.1 车间调度问题2.1.1 车间调度问题的描述车间调度是在满足某些约束（作业的先
