3.5.1 遗传算法的设计步骤............................... 22 3.5.2 编码方式......................................... 22 3.5.3 适配值函数....................................... 24 3.5.4 遗传算子的设计................................... 24 3.5.5 编码参数......................................... 26 3.5.6 遗传算子......................................... 26 3.5.7 算法的终止条件................................... 26
第四章 两机无等待流水车间调度问题仿真 ......................... 27
4.1 流水车间调度问题的描述与数学模型....................... 27 4.2 基于Johnson法则的两机无等待流水车间调度问题仿真....... 28 4.3 遗传算法的设计......................................... 31
4.3.1 编码方案......................................... 31 4.3.2 群体的确定....................................... 31 4.3.3 适应度函数....................................... 31 4.3.4 遗传算子的设计................................... 31 4.4 基于遗传算法的两机无等待流水车间调度问题仿真........... 32 4.5 结果分析............................................... 32 第五章 全文总结 ............................................... 33 参考文献 ...................................................... 34 致 谢 ......................................................... 36 毕业设计小结 .................................................. 37
IV
西北工业大学明德学院本科毕业设计论文
第一章 绪 论
1.1 引 言
伴随着用户对产品需求的快速变化，以及市场竞争的日趋激烈，现代制造企业需要进行多品种、小批量生产，这种生产方式使生产计划、组织和控制变得更加复杂。另外，要求企业对生产过程中所出现的各种信息进行及时反馈和处理，因此，生产调度问题作为生产管理系统的核心内容和关键问题，其研究具有重要的理论和实用价值。企业要进行改革，结合企业的现状，研究改进遗传算法在车间调度的应用，从而合理分配企业资源、提高劳动效率。研究改进遗传算法在车间调度的应用，从而合理分配企业资源、提高劳动效率。
1.2 国内外车间调度问题的研究现状和存在的问题
1.2.1 国内外车间调度问题的研究现状
调度问题的研究始于20世纪50年代，S.M.Johnson提出了解决n/2/F/Cmax和部分特殊的n/3/F/Cmax问题的算法，这是调度理论的开始：直至五十年代末期，许多研究成果主要是针对规模较小的单机和简单的流水车间的问题，提出了解析优化方法，许多研究成果主要是针对规模较小的单机和简单的流水车间问题，提出了解析优化方法，研究范围较窄，但是这些研究却成为经典调度理论的基石。
六十年代，多是利用混合或纯整数规划和分支定界法解决一些有代表性的问题，如Story的研究。同时也有人开始尝试用启发式算法研究此问题，如Gavett提出的方法。六十年代末期，经典调度理论体系初步成型。七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属于NP完全问题或NP一难问题，难以找到多项式算法，因此开始关注启发式算法。Panwalkar总结和归纳出了113条调度规则，并对其进行分类。七十年代末期，经典调度理论趋向成熟。
八十年代初期，Stephen等从三个方面对调度进行了从新考察，对未来发展做了分析和预测，认为理论与实际的结合将会成为研究热点。这个富有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应用到
1
研究中。其中最引人注目的就是以Carnegie-Mellon大学的M.Fox为代表的学者们开展的基于约束传播的ISIS研究，它标志了人工智能开始真正应用与调度问题。八十年代后期，Giffler等人总结了生产调度理论和实际方面的最新研究进展，从七个方面论述了生产调度的技术和方法，认为生产调度无论在理论还是实践上都已突破了传统界限。
九十年代至今，各种方法在生产调度问题的研究中得到了充分的发挥，同时新的研究手段层出不穷。 而Davis是最早把 GA(GeneticAlgorithm，遗传算法)应用于车间调度问题的学者之一，他在使用GA求解车间调度的研究中取得了近似最优解。1985年，Davis发表了关于把GA成功应用于车间调度问题的论文，充分证明了GA在解决车间调度问题中的可行性。此后，很多学者就给予遗传算法的车间调度方面做了大量研究，发表了大量卓有成效的论文，对车间调度这类NP问题的解决提出了具体方案。这些论文中提出了一些具有突破性的新方法，改进并完善了传统GA车间调度中的应用方法，同时通过在解决一些著名的标准检测问题(Ben和nark)的过程中取得了最优(或接近最优)解，进一步证明了遗传算法在解决NP问题方面的有效性。
国内对车间调度的研究起步比较晚，始于90年代。很多企业由于技术上的制约，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在车间调度方面的应用热潮，在这方面也产生了大量的研究成果，不过，研究工作主要集中在清华大学等等CIMS国家重点实验室，但离形成系统的理论和开发出成熟的软件系统还有很长一段距离，因此还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业作业调度算法的研究方面，目前尚处在实验研究阶段。
车间调度问题的高度复杂性和现有计算机条件的局限性决定了不可能一开始就考虑到实际调度问题中的所有因素，因此，实际研究通常是对车间系统进行简化和抽象来解决实际问题。正是在这些现有的理论成果上不断加上约束条件，使得研究问题近似于实际问题。总而言之，随着各种特殊调度问题的攻克和新方法、新设备的出现，车间调度研究正向动态、敏捷、多资源、智能化的方向发展。 1.2.2 研究中存在的问题
由于在实际生产过程中会出现诸多不确定因素，而且调度问题己经被证明
2
NP难题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。从目前文献的研究来看，对于资源分配也没有提出一个切实可行的解决方案，往往都是从某一方面入手，在若干假设的基础上，得出一种理论上的可行解。各种启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得到的调度解的次优性不能进行评估。因此，有必要探索更好的近似最优调度算法，可以考虑通过增加合理的计算时间来提高解的次优性。各种基于统计优化的方法，诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但与别的优化算法类似，也存在着一定程度的枚举、一般来说收敛到最优解较慢，对于判断解的最优性也很困难，在这方面也需要做进一步的研究。
1.3 研究意义与目的
有史以来，有限资源的合理配置和优化利用问题始终是人类社会所面临的最基本经济问题，这个问题贯穿于社会生活的各个方面。从一个国家、社会的宏观经济运行到具体企业的微观经济活动，都要受资源条件的限制。对企业来说，能否对现有资源进行合理配置和充分利用将直接影响到产品的制造成本，进而成为影响企业效益的重要因素。企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中，所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。
车间生产调度是制造系统生产管理的核心，是生产管理和控制系统实现管理技术、运筹技术、优化技术和自动化技术发展的核心。及时准确的生产调度对生产系统的高效运行有着重要的影响。生产管理任务能否顺利的实施与完成，最终要靠合理的生产调度来保证有效。
实用的调度方法和优化技术的研究与应用己成为先进制造技术实践的基础。因此，研究生产调度问题，不仅具有较大的理论意义，而且具有相当大的实用价值。一方面，生产调度问题的研究不仅可以推动相关算法的研究，如遗传算法、神经网络、人工智能等，而且还能在此基础上提出新的算法，这为其他领域类似问题的解决提供了条件和手段；另一方面，一个好的生产调度方案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的竞争力。
随着科学技术的发展，制造行业的生产规模变得越来越大，产品越来越多样
3
