1、I摘要生产计划与生产调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。为了解决实际生产中的车间调度问题，提出了应用改进后的遗传算法解决方案。由于基本遗传算法存在收敛过慢和“早熟” 的问题等，为解决这些问题，引入多色集合理论的围道布尔矩阵进行模型约束，在模型约束下，使编码、解码和变异过程都通过搜索围道布尔矩阵而提高了遗传算法速度，也就提高了整个遗传算法的使用效率，使改进后的遗传算法能够有效的解决实际车间调度问题。关键字：多色集合理论；遗传算法；车间调度IIAbstractProduction planning and scheduling the direc
2、t relation enterprise production efficiency and production cost, effective planning and scheduling algorithms can maximize the efficiency of enterprises. In order to solve the actual production of the workshop scheduling problem, put forward the application of the improved genetic algorithm solution
3、. Due to the basic genetic algorithm has slow convergence and“ premature“ problem, in order to solve these problems, introducing the polychromatic sets theory contour Boolean matrix model constraints, in the model, the coding, decoding and variation process through searching the contour Boolean matr
4、ix and the genetic algorithm to improve the speed, also improved the use of a genetic algorithm efficiency, so that the improved genetic algorithm can effectively solve the actual job shop scheduling problem.Key words: polychromatic sets; genetic algorithm; Job Shop Scheduling目 录摘要 .IAbstract.II1 绪论
5、 .11.1 引言 .11.2 论文研究的意义目的与主要内容 .21.2.1 本课题研究的背景 .21.2.2 本课题研究的意义 .31.2.3 本课题研究的目的 .41.2.4 本课题研究的主要内容 .51.3 生产调度问题 .51.3.1 引言 .51.3.2 车间调度概述 .51.3.3 车间调度的分类 .71.3.4 车间调度现有研究方法 .71.3.5 车间调度研究存在的问题及发展趋势 .92 多色集合理论 .112.1 多色集合理论概述 .112.1.1 多色集合理论基础 .112.1.2 多色集合理论的特点 .122.2 多色集合理论的基本概念 .122.3 多色集合的应用 .1
6、62.3.1 简单车间调度 .162.3.2 机床约束模型 .172.3.3 工序约束模型 .193 遗传算法理论基础 .213.1 遗传算法概述 .213.2 主要参数设计及操作流程 .223.2.1 编码 .223.2.2 适应度函数 .233.2.3 算法参数 .233.2.4 算法终止条件 .243.2.5 操作流程 .263.3 一般遗传算法求解车间调度问题 .264 基于多色集合的遗传算法车间调度系统建模 .294.1 车间调度系统数学模型 .294.2 车间调度系统的约束模型 .304.3 模型约束下的改进遗传算法操作 .334.3.1 基于围道布尔矩阵的约束模型 .334.3.
7、2 模型约束下的染色体编码 .364.3.3 模型约束下的染色体解码 .374.3.4 选择操作 .394.3.5 交叉操作 .394.3.6 模型约束下 的染色体变异 .394.4 实例仿真 .415 总结 .43致谢 .44参考文献 .45中国矿业大学11 绪论1.1 引言随着科学技术的飞速发展和市场竞争日益激烈，越来越多的制造企业开始将大量的人力、财力和物力投入到先进的制造技术和先进的制造模式的研究和实施策略之中。改革开放以来，我国制造科学技术有日新月异的变化和发展，确立了社会主义市场经济体制，但与先进的国家相比仍有一定差距，为了迎接新的挑战，必须认清制造技术的发展趋势，缩短与先进国家的
8、差距，使我国的产品上质量、上效率、上品种和上水平，以增强市场竞争力，因此，对制造技术及制造模式的研究和实施是摆在我们面前刻不容缓的重要任务，以实现我国机械制造业跨入世界先进行列。在古代，社会生产力水平不高，人口又稀少，使得资源相对来说比较丰富，资源的有限性问题难以引起人们的普遍重视。但是自从十八世纪六十年代在英国爆发工业革命后，资本主义生产关系迅速发展，由于人类社会生产力水平的空前飞跃，人类对资源的需求急剧上升，资源的有限性问题逐渐成为人类发展面前的巨大障碍，因此对资源的合理配置与优化利用开始成为一个科学研究的新问题。有限资源的合理配置与优化利用问题是人类社会面临的最基本的经济问题，贯穿于社会
9、生活的各个方面，各个层次，从一个国家、社会的宏观经济运行到企业的微观经济活动，都要受到资源条件的限制约束，人们在对它的研究过程中产生了一个非常重要的理论，就是调度理论。什么是调度？调度就是在满足某些约束的条件下对操作的排序，按照排序给调度目标分配资源和时间，并且使某个执行目标达到最优。调度问题来源于不同的领域，如生产计划、计算机设计、电力传输、军队作战、交通运输、后勤及通讯等。所有调度问题的共同特性是没有一个有效的算法能在采用多项式的有效时间内求出其最优解，它们都是 NP 完全问题。调度问题的复杂性、调度领域的多样性和生产环境的动态性，决定了调度问题的解决单纯依靠人或计算机是难以完成的，必须把
10、人、人工智能技术、数学规划和计算机有机结合起来去研究调度问题。有效的调度优化算法能使现代商业领域增加产出、减少周转时间、减少库存，最终减少生产费用、增加利润和客户满意度，所以调度优化算法性能的好坏对这些行业的高效运作有着重要影响，其研究也具有重要的理论意义和实用价值。基于多色集合的遗传算法车间调度系统建模2车间调度问题是一类重要的组合优化问题，与工业生产领域的关系最为密切。到目前为止，有关车间调度问题的研究已非常深入，也派生出不少新的问题。比如由最初简单的单机调度发展到多机调度，由静态调度发展到动态调度，由确定性调度发展到随机调度等，并且在某一类中，还存在多种形式，如多机调度问题中，还存在同速
11、机调度、恒速机调度、变速机调度等，即使同一个调度问题，还可以根据调度目标的不同而出现不同的调度方法。总之，从广度和深度两个方面而来说，车间调度问题己经发展的相当成熟。不过，由于该类问题(车间调度问题)中的大多数问题为 NP 问题，求解方法层出不穷，有确定性算法、启发式算法、一般搜索算法、智能搜索算法等。本文将对车间调度问题采用一种基于遗传算法的混合调度算法进行求解。在计算机技术高度发展的今天，如何让计算机模拟生产计划的调度过程，并最终给出最简洁、最高效的调度方案，一直以来都是众多计算机学者研究的焦点。利用遗传算法求解车间生产调度问题，一方面能够充分地利用遗传算法的全局搜索能力，在较大规模解空间
12、中寻求全局最优解；另一方面，利用遗传算法的隐式并行性和强鲁棒性等优点，可充分减少问题的求解时间，提高问题的求解效率。1.2 论文研究的意义目的与主要内容1.2.1 本课题研究的背景调度问题的研究始于 20 世纪 50 年代，早在 1954 年 Johnson 对两台机床 FlowShop型调度问题进行了研究，代表着调度理论研究的开始。6070 年代建立了调度理论的主体并重视调度复杂性的研究。大量的研究促使车间调度领域取得了丰硕的成果，也提出了各种各样的算法，建立了不同的理论框架模型。 随着 70 年代后期调度理论研究的深入及各种交叉学科，例如：基于运筹学(OR)方法、基于控制的方法、基于启发式
13、规则的调度方法、基于人工智能的方法、基于知识的调度方法、确定性最优化方法、整数规划、仿真调度方法、启发式图搜索法、模拟退火法、禁忌搜索法以及拉各朗日约束松施法等的发展，又涌现出了许多新的车间调度理论与方法。Davis 是最早把 GA(Genetic Algorithm，遗传算法 )应用于车间调度问题的学者之一，他在使用 GA 求解车间调度的研究中取得了近似最优解。1985 年，Davis 发表了关于把中国矿业大学3GA 成功应用于车间调度问题的论文，充分证明了 GA 在解决车间调度问题中的可行性。此后，很多学者就给予遗传算法的车间调度方面做了大量研究，发表了大量卓有成效的论文，对车间调度这类
14、NPhard 问题的解决提出了具体方案。例如：以 David E Goldberg，Yamada ，Nakano， Fang，Kobayashi 等为代表的一些学者在他们的论文中提出了一些具有突破性的新方法，改进并完善了传统 GA 车间调度中的应用方法，同时通过在解决一些著名的标准检测问题的过程中取得了最优(或接近最优)解，进一步证明了遗传算法在解决 NP 问题方面的有效性。国内对车间调度的研究起步比较晚，始于 90 年代。很多企业由于技术上的制约，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在车间调度方面的应用热潮，在这方面也产生了大量的研究成果，不过，研究工作主要集中在清华
15、大学等等。CIMS(计算机 /现代集成制造系统 )国家重点实验室，但离形成系统的理论和开发出成熟的软件系统还有很长一段距离，因此还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业作业调度算法的研究方面，目前尚处在实验研究阶段。由文献 1可看出虽然遗传算法已经成为一种比较通用的优化算法，因其编码技术和遗传操作比较简单，优化不受限制性条件的约束，但是遗传算法也有其明显的不足之处：对于大规模的组合优化问题，搜索空间大，搜索时间较长；往往会出现早熟收敛的情况；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。文献 2提出了将动态自适应技术搜索速度快和混合启发式算法局部搜索能力强
16、的优点综合到一起的并行动态自适应技术和混合启发式遗传算法，利用混合遗传算法来提高局部搜索能力，利用自适应遗传算法来提高局部搜索速度，此方法明显改善了遗传算法的收敛速度，但是算法复杂，算法空间仍很大。像其它的文献 345的改进方法也都存在这样的问题。1.2.2 本课题研究的意义随着全球经济的一体化和信息技术日新月异的发展，现代企业面临着复杂多变的市场环境。为了响应瞬息万变，难以预测的国内外市场需求，迎接竞争与挑战，适应时代潮流的发展，企业必须能够具有动态地调整其生产制造策略和模式的能力，以支持企业对全球竞争、产品创新和市场变化的快速响应。这样，迫使制造企业从原来一元化、单品种、大批量、流水线式的
17、大批量制造的生产方式，逐渐向多元化、多品种、小批量、基于多色集合的遗传算法车间调度系统建模4高柔性、相对复杂的敏捷制造的生产方式转变，目前，敏捷制造逐渐成为现代制造业的主流。生产调度，即对生产过程进行作业计划。作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。车间生产调度的主要任务是针对某一任务集(产品制造)，在尽可能满足各种约束条件(如交货期，工艺特性，设备状态、资源配置情况等等)的前提下，合理配置加工过程的各种资源，减少零件的加工准备、等待与传送时间，从而提
18、高设备利用率与生产效率，降低生产成本，以获得产品制造时间或者成本的最优化。无论是虚拟车间还是真正的生产车间，要能迅速响应客户的要求，其关键是能在很短的时间内，以高质量、可承受的价格生产出用户满意的产品。产品设计的再快再好，工艺再先进，如不能及时制造出来，或生产出来成本过高，用户是不会感到满意的。由此可见，车间生产调度方面的研究，实际上正是实现敏捷制造思想重要而关键的领域，是一需要在理论研究和实际应用中进行探讨的问题，它对敏捷制造企业的许多使能子系统都有着非常重要的影响。随着市场竞争的逐步升级，不断的激励着企业界和学术界去寻找新的调度模式和更好的调度优化方法，而激励人们这么做的最主要的因素就是：
19、合理的、优化的生产调度和资源配置能提高资源的利用率和操作管理水平，提高企业的生产效率，降低产品的生产成本，最大限度的满足客户的需要，生产出在市场上更具竞争力的产品，给企业带来更大的经济效益。因为车间调度问题是生产调度不可或缺的调度之一，所以研究车间调度的合理解决方法是必要的，提高车间调度的效率就是为企业创造价值。1.2.3 本课题研究的目的根据课题存在的问题，本文在现有车间调度遗传算法研究的基础上，结合多色集合理论，解决作业车间调度问题，不仅具有重要的现实意义，而且具有深远的理论意义。车间作业调度就是根据产品制造需求合理分配产品制造资源，进而达到合理利用产品制造资源，提高企业经济效益的目的。它是产品制造行业中共存的问题，它与 CIMS 中的工厂管理，产品制造层次紧密相关，是 CIMS 领域中研究的重要课题。同时车间作业调度因其离散性，动态性，多机性，多变量性和耦合性等典型的 NP-hard 性，其研究必然会对NP 问题的研究起到有意义的影响。JSP 问题研究需要方法上的改进，尽管 JSP 问题的各个研究流派提出了很多研究方法，但这些方法在不同程度上存在着一定的缺点，若要进
