基于多色集合的遗传算法-毕业设计论文.doc

摘要
生产计划与生产调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。为了解决实际生产中的车间调度问题，提出了应用改进后的遗传算法解决方案。由于基本遗传算法存在收敛过慢和“早熟”的问题等，为解决这些问题，引入多色集合理论的围道布尔矩阵进行模型约束，在模型约束下，使编码、解码和变异过程都通过搜索围道布尔矩阵而提高了遗传算法速度，也就提高了整个遗传算法的使用效率，使改进后的遗传算法能够有效的解决实际车间调度问题。

关键字：多色集合理论；遗传算法；车间调度

Abstract
Production planning and scheduling the direct 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. 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 matrix 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

I

目 录
摘要 I
Abstract II
1 绪论 1
1.1 引言 1
1.2 论文研究的意义目的与主要内容 2
1.2.1 本课题研究的背景 2
1.2.2 本课题研究的意义 3
1.2.3 本课题研究的目的 4
1.2.4 本课题研究的主要内容 5
1.3 生产调度问题 5
1.3.1 引言 5
1.3.2 车间调度概述 5
1.3.3 车间调度的分类 7
1.3.4 车间调度现有研究方法 7
1.3.5 车间调度研究存在的问题及发展趋势 9
2 多色集合理论 11
2.1 多色集合理论概述 11
2.1.1 多色集合理论基础 11
2.1.2多色集合理论的特点 12
2.2 多色集合理论的基本概念 12
2.3多色集合的应用 16
2.3.1 简单车间调度 16
2.3.2 机床约束模型 17
2.3.3 工序约束模型 19
3 遗传算法理论基础 21
3.1遗传算法概述 21
3.2主要参数设计及操作流程 22
3.2.1编码 22
3.2.2适应度函数 23
3.2.3算法参数 23
3.2.4算法终止条件 24
3.2.5操作流程 26
3.3 一般遗传算法求解车间调度问题 26
4 基于多色集合的遗传算法车间调度系统建模 29
4.1车间调度系统数学模型 29
4.2车间调度系统的约束模型 30
4.3 模型约束下的改进遗传算法操作 33
4.3.1基于围道布尔矩阵的约束模型 33
4.3.2模型约束下的染色体编码 36
4.3.3模型约束下的染色体解码 37
4.3.4选择操作 39
4.3.5交叉操作 39
4.3.6模型约束下的染色体变异 39
4.4实例仿真 41
5 总结 43
致谢 44
参考文献 45

中国矿业大学
1 绪论
1.1 引言
随着科学技术的飞速发展和市场竞争日益激烈，越来越多的制造企业开始将大量的人力、财力和物力投入到先进的制造技术和先进的制造模式的研究和实施策略之中。改革开放以来，我国制造科学技术有日新月异的变化和发展，确立了社会主义市场经济体制，但与先进的国家相比仍有一定差距，为了迎接新的挑战，必须认清制造技术的发展趋势，缩短与先进国家的差距，使我国的产品上质量、上效率、上品种和上水平，以增强市场竞争力，因此，对制造技术及制造模式的研究和实施是摆在我们面前刻不容缓的重要任务，以实现我国机械制造业跨入世界先进行列。
在古代，社会生产力水平不高，人口又稀少，使得资源相对来说比较丰富，资源的有限性问题难以引起人们的普遍重视。但是自从十八世纪六十年代在英国爆发工业革命后，资本主义生产关系迅速发展，由于人类社会生产力水平的空前飞跃，人类对资源的需求急剧上升，资源的有限性问题逐渐成为人类发展面前的巨大障碍，因此对资源的合理配置与优化利用开始成为一个科学研究的新问题。有限资源的合理配置与优化利用问题是人类社会面临的最基本的经济问题，贯穿于社会生活的各个方面，各个层次，从一个国家、社会的宏观经济运行到企业的微观经济活动，都要受到资源条件的限制约束，人们在对它的研究过程中产生了一个非常重要的理论，就是调度理论。
什么是调度？调度就是在满足某些约束的条件下对操作的排序，按照排序给调度目标分配资源和时间，并且使某个执行目标达到最优。调度问题来源于不同的领域，如生产计划、计算机设计、电力传输、军队作战、交通运输、后勤及通讯等。所有调度问题的共同特性是没有一个有效的算法能在采用多项式的有效时间内求出其最优解，它们都是NP完全问题。调度问题的复杂性、调度领域的多样性和生产环境的动态性，决定了调度问题的解决单纯依靠人或计算机是难以完成的，必须把人、人工智能技术、数学规划和计算机有机结合起来去研究调度问题。
有效的调度优化算法能使现代商业领域增加产出、减少周转时间、减少库存，最终减少生产费用、增加利润和客户满意度，所以调度优化算法性能的好坏对这些行业的高效运作有着重要影响，其研究也具有重要的理论意义和实用价值。
车间调度问题是一类重要的组合优化问题，与工业生产领域的关系最为密切。到目前为止，有关车间调度问题的研究已非常深入，也派生出不少新的问题。比如由最初简单的单机调度发展到多机调度，由静态调度发展到动态调度，由确定性调度发展到随机调度等，并且在某一类中，还存在多种形式，如多机调度问题中，还存在同速机调度、恒速机调度、变速机调度等，即使同一个调度问题，还可以根据调度目标的不同而出现不同的调度方法。总之，从广度和深度两个方面而来说，车间调度问题己经发展的相当成熟。不过，由于该类问题(车间调度问题)中的大多数问题为NP问题，求解方法层出不穷，有确定性算法、启发式算法、一般搜索算法、智能搜索算法等。本文将对车间调度问题采用一种基于遗传算法的混合调度算法进行求解。
在计算机技术高度发展的今天，如何让计算机模拟生产计划的调度过程，并最终给出最简洁、最高效的调度方案，一直以来都是众多计算机学者研究的焦点。利用遗传算法求解车间生产调度问题，一方面能够充分地利用遗传算法的全局搜索能力，在较大规模解空间中寻求全局最优解；另一方面，利用遗传算法的隐式并行性和强鲁棒性等优点，可充分减少问题的求解时间，提高问题的求解效率。
1.2 论文研究的意义目的与主要内容
1.2.1 本课题研究的背景
调度问题的研究始于20世纪50年代，早在1954年Johnson对两台机床Flow．Shop型调度问题进行了研究，代表着调度理论研究的开始。60～70年代建立了调度理论的主体并重视调度复杂性的研究。大量的研究促使车间调度领域取得了丰硕的成果，也提出了各种各样的算法，建立了不同的理论框架模型。
随着70年代后期调度理论研究的深入及各种交叉学科，例如：基于运筹学(OR)方法、基于控制的方法、基于启发式规则的调度方法、基于人工智能的方法、基于知识的调度方法、确定性最优化方法、整数规划、仿真调度方法、启发式图搜索法、模拟退火法、禁忌搜索法以及拉各朗日约束松施法等的发展，又涌现出了许多新的车间调度理论与方法。
Davis是最早把GA(Genetic Algorithm，遗传算法)应用于车间调度问题的学者之一，他在使用GA求解车间调度的研究中取得了近似最优解。1985年，Davis发表了关于把GA成功应用于车间调度问题的论文，充分证明了GA在解决车间调度问题中的可行性。此后，很多学者就给予遗传算法的车间调度方面做了大量研究，发表了大量卓有成效的论文，对车间调度这类NP—．hard问题的解决提出了具体方案。例如：以David E Goldberg，Yamada，Nakano， Fang，Kobayashi等为代表的一些学者在他们的论文中提出了一些具有突破性的新方法，改进并完善了传统GA车间调度中的应用方法，同时通过在解决一些著名的标准检测问题的过程中取得了最优(或接近最优)解，进一步证明了遗传算法在解决NP问题方面的有效性。
国内对车间调度的研究起步比较晚，始于90年代。很多企业由于技术上的制约，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在车间调度方面的应用热潮，在这方面也产生了大量的研究成果，不过，研究工作主要集中在清华大学等等。CIMS(计算机/现代集成制造系统)国家重点实验室，但离形成系统的理论和开发出成熟的软件系统还有很长一段距离，因此还在投入大量的人力和物力进行该方面的研究，特别是在开展对车间作业作业调度算法的研究方面，目前尚处在实验研究阶段。
由文献[1]可看出虽然遗传算法已经成为一种比较通用的优化算法，因其编码技术和遗传操作比较简单，优化不受限制性条件的约束，但是遗传算法也有其明显的不足之处：对于大规模的组合优化问题，搜索空间大，搜索时间较长；往往会出现早熟收敛的情况；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。
文献[2]提出了将动态自适应技术搜索速度快和混合启发式算法局部搜索能力强的优点综合到一起的并行动态自适应技术和混合启发式遗传算法，利用混合遗传算法来提高局部搜索能力，利用自适应遗传算法来提高局部搜索速度，此方法明显改善了遗传算法的收敛速度，但是算法复杂，算法空间仍很大。像其它的文献[3][4][5]的改进方法也都存在这样的问题。
1.2.2 本课题研究的意义
随着全球经济的一体化和信息技术日新月异的发展，现代企业面临着复杂多变的市场环境。为了响应瞬息万变，难以预测的国内外市场需求，迎接竞争与挑战，适应时代潮流的发展，企业必须能够具有动态地调整其生产制造策略和模式的能力，以支持企业对全球竞争、产品创新和市场变化的快速响应。这样，迫使制造企业从原来一元化、单品种、大批量、流水线式的大批量制造的生产方式，逐渐向多元化、多品种、小批量、高柔性、相对复杂的敏捷制造的生产方式转变，目前，敏捷制造逐渐成为现代制造业的主流。生产调度，即对生产过程进行作业计划。作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。车间生产调度的主要任务是针对某一任务集(产品制造)，在尽可能满足各种约束条件(如交货期，工艺特性，设备状态、资源配置情况等等)的前提下，合理配置加工过程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备利用率与生产效率，降低生产成本，以获得产品制造时间或者成本的最优化。无论是虚拟车间还是真正的生产车间，要能迅速响应客户的要求，其关键是能在很短的时间内，以高质量、可承受的价格生产出用户满意的产品。产品设计的再快再好，工艺再先进，如不能及时制造出来，或生产出来成本过高，用户是不会感到满意的。由此可见，车间生产调度方面的研究，实际上正是实现敏捷制造思想重要而关键的领域，是一需要在理论研究和实际应用中进行探讨的问题，它对敏捷制造企业的许多使能子系统都有着非常重要的影响。随着市场竞争的逐步升级，不断的激励着企业界和学术界去寻找新的调度模式和更好的调度优化方法，而激励人们这么做的最主要的因素就是：合理的、优化的生产调度和资源配置能提高资源的利用率和操作管理水平，提高企业的生产效率，降低产品的生产成本，最大限度的满足客户的需要，生产出在市场上更具竞争力的产品，给企业带来更大的经济效益。因为车间调度问题是生产调度不可或缺的调度之一，所以研究车间调度的合理解决方法是必要的，提高车间调度的效率就是为企业创造价值。
1.2.3 本课题研究的目的
根据课题存在的问题，本文在现有车间调度遗传算法研究的基础上，结合多色集合理论，解决作业车间调度问题，不仅具有重要的现实意义，而且具有深远的理论意义。车间作业调度就是根据产品制造需求合理分配产品制造资源，进而达到合理利用产品制造资源，提高企业经济效益的目的。它是产品制造行业中共存的问题，它与CIMS中的工厂管理，产品制造层次紧密相关，是CIMS领域中研究的重要课题。同时车间作业调度因其离散性，动态性，多机性，多变量性和耦合性等典型的NP-hard性，其研究必然会对NP问题的研究起到有意义的影响。JSP问题研究需要方法上的改进，尽管JSP问题的各个研究流派提出了很多研究方法，但这些方法在不同程度上存在着一定的缺点，若要进一步的研究JSP问题，就必须对这些方法进行改进。本文用多色集合的围道布尔矩阵改进了遗传算法，以改进的遗传算法作为求解JSP问题的主要手段。
1.2.4 本课题研究的主要内容
首先本文详细叙述了车间调度问题、遗传算法和多色集合理论三个模块，其中，第一章绪论，介绍了车间调度问题，概述了车间调度的发展、分类、现有的研究方法和凸显的问题所在，以及本文的研究背景、研究意义和目的。
第二章多色集合理论，则重点讲了多色集合的基本理论，它的特点和基本概念，举了一个简要的约束模型例子，说明多色集合的围道布尔矩阵在车间调度约束模型中的应用。
第三章遗传算法理论基础，简要介绍了遗传算法的产生与发展、基本原理和实现步骤，从遗传算法的产生到现有发展状况都有论述到，并且详细论述了遗传算法的主要参数和运用设计过程。
其后，在以上三模块的基础上，提出基于多色集合的遗传算法车间调度系统建模的过程。
第四章基于多色集合的遗传算法车间调度系统建模，就说明了基于多色集合的遗传算法车间调度系统建模的各个步骤，阐述了怎样在编码、解码和编译过程中，应用围道布尔矩阵提高算法速度的，并且进行了实例仿真，使改进的遗传算法的优越性体现出来。
最后，第五章总结，概括了全文主要工作，提出本文的主要结论。
1.3 生产调度问题
1.3.1 引言
生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的。现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是非常重要的。
1.3.2 车间调度概述
1954年，Johnson研究了两台机床的流水车间调度问题。这标志着调度理论研究的开始。由于调度问题的理论价值和实用意义，在后来的几十年中，有几万多篇关于调度问题的文献发表。总的来说，车间调度就是对一个可用的制造资源集在时间上进行加工任务(加工工件)集的分配，将作业(加工操作)均衡地安排到各机器，并合理地安排作业的加工次序和开始时间，同时优化一些性能指标，在执行这些作业或者任务时需要满足某些限制条件，如作业的到达时间、完工的限定时间、作业的加工顺序、资源对加工时间的影响等。典型的车间调度问题包括一个待加工零件集合，每个零件包括一个工序集合，各工序需要占用机床等生产资源，并且要按照一定的工艺路线进行加工；不同机床加工的工序可以不同；调度的目的就是为零件合理地分配机床等资源，并合理地安排加工时间，在满足约束条件的同时，使一些指标最优。从数学规划的角度看，车间调度问题可表达为在等式或不等式约束下，对一个或多个目标函数的优化。在实际的制造自动化(柔性自动化)系统的车间调度中，由于要考虑刀具、托盘和物料搬运系统的调度问题，因此不但包括作业调度问题，而且也应考虑资源分配问题。
一般车间调度问题可以描述为：n个工件在m台机器上加工，一个工件分为k道工序，每道可以在若干台机器上加工。每一台机器在每个时间只能加工某个工件的某道工序，只能在上道工序加工完成才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束[6]。
车间调度问题是多个工件在有限的机器上加工，每台机器在切换不同的工件加工同时又需要一定的生产加工准备时间。切换加工的次数越多越有利于减少工件的库存，但导致生产率的下降。因此，需要在库存成本与切换加工次数频率之间寻求一个动态的平衡。生产的柔性体现在设备的使用和设备的安排两个方面，设备使用的柔性是指设备可用于多个零件的多道工序加工，设备安排的柔性是指工件的设备加工路径，而不是固定或预先确定的。具有可选的路径，可以通过将若干设备组作为一条或者多条生产线加工一种工件，使得该工件的生产率最大。
车间调度的另一类研究集中于柔性制造系统(FMS)，FMS由一系列NC数控设备组成，NC能够单独加工多个工件，在选择了待加工工件后，所需刀具必须分配到该设备的工具集中。FMS问题包括工件选择分配、设备分组、生产率确定和设备负荷、工具分配等问题，它的约束包括设备工具集的容量限制、设备可用时间和设备负荷等。
综上所述我们可以得到车间调度问题的特点为：
建模、计算复杂性：车间中机器、工件、缓存和搬运系统之间关系复杂，即相互影响又相互作用。还要考虑每个工件之间的安装时间、加工时间、完成时间以及操作顺序等，因而相当复杂。
动态随机性：在工件加工过程中有很多随机和不确定因素，如工件到达时间的不确定性，上件的加工完成时间，实际工件的加工时间都有一定的随机性．
多约束性：调度中受到很多约束条件的限制，资源的数量、缓存的容量、工件到期时间，以及工件的操作顺序等。
多目标性：调度的目标很多，目标之间往往又相互冲突。如：基于工件加工完成时间的目标，基于工件到期时间的目标和基于生产成本的目标。
1.3.3 车间调度的分类
根据研究的侧重点不同，车间调度问题根据资源约束种类和数量的不同可分为单个资源车间调度(Single Resource Constrained)、两个资源车间调度(Dual Resource Constrained)和多资源车间调度(Multiple Resource Constrained)；根据零件和车间构成不同可分为：生产车间调度(Job Shop)、流水车间调度(Flow shop)、开放车间调度(Open Shop)、单车间调度(single shop)。
根据加工工件的特点也可将调度问题分为静态调度和动态调度问题：
(1) 静态车间调度(static Scheduling)：所有的零件在开始调度时刻就已经准备就绪，不考虑零件在加工过程中出现的突发事件。
(2) 动态车间调度(Dynamic Scheduling)：车间调度要求考虑零件在加工过程中出现的各种突发事件。这种调度方式要求调度能随时响应车间加工能力的变化，在有突发事件出现后，能立即根据当时的车间加工能力，对待加工的零件进行重新调度。
1.3.4 车间调度现有研究方法
一般的调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进行分类。由于实际中生产环境是千差万别的，那么一个调度算法就应该根据其是否能适合对应的生产环境的重要特征进行评估。在对调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各种新的相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优化方法，我们归纳这些优化方法如下：
(1) 确定性最优化方法
该方法主要通过对车间调度问题建立一个整数规划模型，采用基于枚举思想的分析定界或动态规划法进行求解，分析定界法有很多，其主要不同点在于分析规则、定界机制和上界的产生等二个方面的差异。这类方法从理论上来说是能求得最优解，但通常由于计算复杂不能获得真正的实用价值。
(2) 基于启发式规则的调度方法
启发式方法，并不是在多项式时间内求得问题的最优解，而是在计算时间和调度效果之间进行折中，以较小的计算量来得到最优或次优解，此方法因调度规则易于实现，计算复杂度低，能够用于动态实时调度系统中，许多年来一直受到广泛关注和研究，但是启发式规则一般不具备全局优化的特点。
(3) 基于智能的调度方法
近年来受实际需要的推动，基于知识的智能调度系统和方法的研究取得了很大的进展，基于知识的调度方法是利用模型和知识，通过模拟和推理等手段为人的决策行为提供支持，从而使人们可以根据车间的不同情况做出相应的更符合实际的决策。其中最常见的就是专家系统，但是此方法对新的调度环境的适应性较差并且开发周期长、成本昂贵。
(4) 仿真调度方法
由于制造系统的复杂性，很难用一个精确的解析模型来进行描述分析，而通过对仿真模型的运行收集数据，就能对实际系统进行性能，状态方面的分析，从而能对系统采用合适的控制调度方法。但是该方法不可避免存在以下问题：a)缺乏理论意义；b)应用仿真进行生产调度的费用很高：c)仿真的准确性程度受编程人员的判断和技巧的限制。
(5) 基于模糊数学理论的方法
客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定性；不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点，许多学者把它引入了调度领域。但与专家系统相似，这种方法同样存在开发周期长、需要丰富的调度经验和知识等缺点。
(6) 模拟退火法
模拟退火法(SA)是将组合优化问题与统计力学的热平衡问题类比，通过模拟退火过程，可找到全局最优解。模拟退火法的改进算法有加温退火法、记忆退火模拟退火法。可以用于具有最小Make span指标的Flow Shop排序问题。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢。很难用于实时动态调度环境。
(7) 禁忌搜索法
对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方法，Glover首次叙述了它的基本原理。该方法已经用于解决flow shop调度问题，但是禁忌搜索的应用需要较多的技巧，不方便实现。
(8) 神经网络优化
Hopfield神经网络模型可以求解各种有约束的优化问题，随机Hopfield也可以用于解决job shop的调度问题，但由于涉及的变量太多，计算效率低，很难解决实际调度问题。
(9) 遗传算法
20世纪末美国Michigan大学的J.H.Holland提出了一种新的并行优化搜索方法：遗传算法(genetic algorithm),它是一种基于进化论的优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全区性优化搜索。它以其很强的并行性和很高的计算效率正日益受到人们的关注。总之，遗传算法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在计算速度较慢的问题。
1.3.5 车间调度研究存在的问题及发展趋势
虽然遗传方法能够解决车间调度中的一些问题，但由于实际中的情况千差万别，所以不能很精确的得到一个最优解，只能从某一方面出发如最短时间，最优路径等，从而得出较近似的结果，在调度问题的理论研究中，大多研究是关于经典的调度问题算法，而实际中的问题又有好多不确定因素，和经典调度问题中的相比较相差较大。在实际车间调度中，车间计划与车间调度往往是不同的，这就有可能造成计划在实际调度中存在一些问题，如何将计划与调度综合考虑，从而进行优化达到满意结果。
综上所述，我们不难看出，虽然对车间调度领域的研究已有很长的历史，但是至今尚未形成一套系统的理论与方法，理论研究和实际应用之间还存在着很大的差距。今后调度问题的研究应该向下面几个方向发展:
(1) 实用化
一些理论上的最优调度方法能够提供最优调度，但由于计算复杂性大，并且忽略了很多实际的因素，离应用还有很大的差距。因此如何综合运用现有优化算法，真正提高车间调度的信息化水平有待进一步的研究。
(2) 集成化
探索车间计划与调度的集成。集合回答应该生产什么，而调度则回答怎样生产。两者是相互联系的，应该建立一个集成系统。
(3) 高效智能化
寻找新的调度算法，该算法应该能够快速、高效的找到大规模调度问题的最优解或次优解，并能对找到的解进行评估。
(4) 柔性化
在传统的车间调度问题的研究中，仅考虑每一工件具有唯一确定加工工艺路线的情况。随着加工技术、自动化技术的发展，特别是柔性加工系统(MFS)的出现，工件加工工艺路线必须唯一确定的传统限制己被突破，工件具有多个可选择的加工路线，即路径柔性己成为生产的实际需求。
总之，对于生产调度问题的研究，随着应用数学理论的进一步发展，必然朝着实用化、集成化、高效智能化、柔性化的方向发展。

2 多色集合理论
2.1 多色集合理论概述
2.1.1 多色集合理论基础
在机械加工工艺和机械装配工艺过程设计自动化领域，在长期研制开发对象仿真的分层递阶系统的过程中，俄罗斯著名的飞行器设计与制造专家巴普洛夫教授(V．V．Pavlov)于1988年提出了多色图的概念，于1995年提出了多色集合的概念，于2002年提出了多色集合理论(Theory of Polychromatic Sets，简称TPS)的体系结构[7]。
首先多色集合是一种新的系统理论和信息处理工具。传统集合是元素的全体。集合中任意两个元素仅仅是名字上的不同，它们的任何其他性质在形式上并没有表示出来。在多色集合中，集合整体本身及其组成元素都能够被同时涂上一些不同的颜色，用来表示研究对象及其元素的性质。在使用多色集合这一新的信息处理工具时，其核心思想是使用形式上相同的数学模型来仿真不同的对象(产品、设计过程、工艺过程和生产系统)，使仿真系统更加具有柔性。由于存在形式上相同的数学模型，在问题的形式化研究方面前进了一步，具有高度的概括性。这是该信息处理工具的一个优点，也是它在理论上的一个贡献。其次，多色集合这一信息系统的体系是一个递阶系统。在集合层和逻辑层组织和处理信息，在数量解决底层具体数量大小问题。该信息系统能处理大量的信息，能用来仿真大型、复杂机械产品。再次，多色集合数学模型的成分是多色集合的元素、统一颜色和个人颜色及其相互关系和联系。多色集合的统一颜色描绘了多色集合整体的性质，它的个人颜色描绘了多色集合元素的性质。现实系统中普遍存在着层次结构，而多色集合实际上是刻画系统层次结构中构成性关系和相干性关系的数学模型，其将系统及其元素、系统层次结构中的构成性关系、相干性关系分别抽象为多色集合及其元素、集合整体性质与组成元素性质之间的关系、组成元素性质之间的关系。
虽然在此之前，多色集合的数学模型还没有应用于车间调度的系统设计，但它能方便地描绘加工机床与工序之间的相互关系和联系。所以，多色集合的理论能在车间调度系统建模中发挥作用。最后，该方法很方便用于编程。
2.1.2多色集合理论的特点
多色集合是一种新的信息处理数学工具，其不仅能描绘系统中元素的性质，还能描述系统整体的性质，同样也能描绘元素和系统整体性质间不同的关系和联系。多色集合使用形式上相同的数学模型来仿真不同的对象，使得仿真系统更加具有柔性，从而为建立产品生命周期设计的统一信息处理自动化系统奠定了理论基础。其特点如下：
(1) 多色集合可以建立形式上相同的数学模型，这就使得该问题在形式化研究方面有了统一的形式，因而具有明显的优势。
(2) 多色集合所建立信息系统的体系是一个递阶系统，它在集合层和逻辑层组织和处理信息，在数量层解决底层具体数量大小问题。
(3) 该系统能处理大量的信息，在大型、复杂机械系统中都可以得到应用。
(4) 多色集合的数学模型能将复杂机械系统的各种性质、属性、参数、特征、指标等技术概念之间的相互关系方便而简洁的描绘出来。
(5) 多色集合可方便使用于计算机编程，适用于建立自动设计系统的不同数学模型之间的接口，方便描绘加工系统。
(6) 多色集合应用广泛，既可以在产品建模、过程优化等关键技术中发挥重要作用，也会在管理学、经济学等方面得到重要应用。多色集合是一个新的非常有发展前途的信息处理工具。
2.2 多色集合理论的基本概念
传统集合表示的是元素的全体，记为 （2-1）
实际上，集合中任意两个元素都是不同的，但是在（2-1）式中元素之间只是名字不同，它们任何别的性质在形式上都没有表示出来，在多色集合中，集合整体本身和它的组成元素都能够同时被涂上一些不同的颜色,用以表示研究对象及其组成元素的性质。
(1) 着色
对于多色集合中的元素，颜色集合对应每个元素，其中，颜色集合对应集合整体。
多色集合整体的颜色成分和多色集合元素的颜色成分包含于统一的颜色集合。
；，其中和称之为着色。
用多色集合的结构表示仿真对象的时候，其对象的性质或者其元素的某个性质，和对象的颜色以及元素的颜色相对应。
(2) 围道
围道即是多色集合中的颜色，在应用中代表被仿真对象的性质、属性、特性等，是系统技术概念的抽象和概括。一般用多色集合和多色图对复杂生产系统或进行机械产品信息仿真时，常常用“围道”这一概念替换“颜色”这一术语。
(3) 个人着色
属于元素本身的颜色集合即称之为这个元素的个人着色[8]。多色集合中所有元素的个人着色可表示如下：

其中，如果存在关系并且则
元素的个人着色由上式中第行的元素的成分确定，即当取l的时候，与之间存在约束关系；当取0的时候，与之间不存在约束。其形式化表示如下：

(4) 统一着色
作为统一对象的多色集合整体的颜色被称为统一颜色，这些颜色的所有组成被称为统一着色。矩阵描述组成元素与多色集合统一颜色的相关关系如下：

其中如果存在关系并且则
元素的个人着色由上式中第行的元素的成分确定，即当取l的时候，与之间存在约束关系；当取0的时候，与之间不存在约束。其形式化表示如下：

(5) 统一颜色
组成多色集合的元素的个人颜色的存在是统一颜色存在的首要原因。统一颜色的存在是以元素或几个这样元素的同名个人颜色存在为前提的，考虑到现实对象和系统仿真的特点，可以允许的存在不仅仅取决于元素的同名个人颜色，而且取决于任何别的颜色。可用布尔矩阵表示如下：

其中如果存在关系并且则
元素的个人着色由上式中第行的元素的成分确定，即当取l的时候，与之间存在约束关系；当取0的时候，与之间不存在约束。其形式化表示如下：

(6) 统一颜色的体
当元素存在时，如果也存在，则元素的组成：就被称为该统一颜色的体。

其中如果存在关系并且则
元素的个人着色由上式中第行的元素的成分确定，即当取l的时候，与之间存在约束关系；当取0的时候，与之间不存在约束。其形式化表示如下：

(7) 多色集合理论的数学表达式
多色集合的数学表达式是由6个成分构成，即

其中⋯表示元素的集合；
⋯表示多色集合元素个人颜色；
⋯表示多色集合统一颜色；
⋯表示多色集合所有元素的个人着色；
⋯表示多色集合的统一着色和元素同名个人颜色的相互关系；
⋯-表示多色集合统一颜色存在的所有体的元素的组成。
在现实系统仿真时，并不需要考虑所有元素个体，应依照实际情况考虑其中的部分属性。此外，还应根据需要描绘多色集合的其他性质。
(8) 多色图
普通的图可记为，其中是节点的集合，是连接节点边的集合，但是这种传统的图论工具不可能同时既描绘图的节点和边的组成，又描绘图的节点和边所具有的不同性质[9]。在多色图中，任何节点和任何边都可以同时被涂上一些不同的颜色，这是多色图和单色图的区别。由于颜色具有对应对象的性质，不同颜色能描绘不同的性质，因此第种颜色所对应的性质为，第种颜色所对应的性质为等。在一般情况下，多色图由组成.其中，描绘多色图整体的性质，描绘节点及其性质，而描绘边及其性质。
2.3多色集合的应用
2.3.1 简单车间调度
根据车间调度问题描述可知，车间调度问题主要受工序约束和机床约束（4.2节有具体叙述），下面结合实例如何应用多色集合理论描述这两个约束，其它车间调度任务中的待加工工序受到的工序约束和机床约束都可以应用同样的方法描述：
(1) 单品种单批量
假设有1个待加工工件，共有6道工序，6台机床，各工序具体可加工的机床及对应
表2-1工序机床加工信息
机床
工序

1
25

23

2

15

17

3

30

35
4
22

26

5

30

32
6

31

34

的加工时间如表2-1所示。
注意： ，，与，，分别为同类机床。在进行生产排产时，需要考虑两类基本约束：机床约束与工序约束。
(2) 多品种多批量
假设有5个待加工工件，共有12道工序，6台机床，各工序具体可加工的机床及对应的加工时间如表2-2所示。注意，工件和机床是连续编号的，编号按照从小到大的顺序。
表2-2 工序加工机床及加工时间
工件
工序
机床及对应加工时间
序号

1
11
5
3

1
12

7

2
2
21

6

3
22

3
4
4
23

4
6

5
3
31
7

6
4
41

9

7
42

10
8
43
4
5
8

9
44

6
5

10
5
51

2

11
52

3

5
12
2.3.2 机床约束模型
(1) 单品种单批量
由表2-1的信息，也可得出另一约束描述，图2-1工序-机床围道布尔矩阵，表示了表2-1所示所有工序和机床的机床约束关系模型。
注意： ，，与，，分别为同类机床。在进行生产排产时，需要考虑两类基本约束：机床约束与工序约束。
机床约束：(1) 每台机床每一时刻只能加工一道工序；(2) 每台机床的工作量不能超过其生产能力，若超过此机床即为产线的瓶颈设备。