《1 引言》

1 引言

调度问题就是在一定时间水平上合理分配资源, 以达到预先设定任务的指标[1]。它来源于柔性制造系统、生产计划、计算机设计及通信等诸多生产和作业领域。被证明是NP难题后, 对其的研究主要集中于纯确定型生产调度问题, 必须对真实环境进行大量的限制、简化和假设, 其模型描述能力有限。传统的模型也无法充分利用经验知识, 而在实际调度中存在大量的模糊因素。所以, 在应用到实际过程时难以得到满意的结果。随着模糊数学的发展, 模糊的思想被运用到调度领域以助于决策者进行有效决策[2], 因此形成非确定性调度的一个重要分支——模糊调度。

建模是生产调度与过程优化的基础, 国内外已作了很多研究。总的来说, 生产调度方法可分为精确算法 (如运筹学方法) 和近似算法。近似方法又分为两大类:基于排序的方法和基于分派规则的方法[3]。目前发展较成熟的近似算法有Gantt图、关键路径法CPM和计划评审技术PERT、 系统仿真方法、 基于知识的方法、 启发式方法、 基于模糊数学理论的方法[4,5]等, 各种算法的组合应用也已成为解决优化调度问题很有前途的方法[6]。现有方法最主要的问题, 一是难以同时处理数据和语言两方面的信息, 从而难以完全描述复杂系统特性, 二是缺少统一的系统模型。由此, 模糊建模的必要性和重要性可见一斑。对模糊建模的综述性文章[6], 大都是从某一具体的角度介绍了其研究成果与进展, 而缺乏综合性的分析与总结。因此, 笔者回顾和总结模糊建模方法的理论与研究成果, 包括模糊建模的类型、形式, 各自的优缺点, 以及未来的发展方向。

《2 生产调度模糊建模方法》

2 生产调度模糊建模方法

现代生产系统是一个包含着人、材料、设备等的复杂大系统[7], 影响这个系统效能的内外因素又是大量不确定的、模糊的经验和知识, 其计划和调度一般都极为复杂。传统生产调度建模方法与模糊集合论的结合, 形成了一个很重要的方向, 这方面的研究正处于如火如荼中。模糊建模方法主要包括数学描述型和参数辨识型两大类型。

《2.1数学描述型 (mathematically expressed) ——模糊规划》

2.1数学描述型 (mathematically expressed) ——模糊规划

普通的规划问题其约束条件和目标函数都是清晰、明确的。但在很多实际问题中, 约束条件和目标函数都可能具有模糊性, 比如约束条件是有弹性的, 约束或目标函数有模糊系数[8], 变量是模糊的[9]等, 这类在模糊环境即模糊约束或模糊目标下的数学规划问题称为模糊规划。通常, 模糊线性规划 (FLP) 数学模型如下:

maxz=cx,s.t.  A≤b‚  x≥0

模糊建模是指从模糊信息的描述到建立一个适当的数学模型的过程[6]。对于一个复杂的生产调度问题, 一般情况下, 建立模糊模型由3个基本环节组成: a. 基于对问题本身的理解, 分析存在的那些模糊信息以及出现的形式和方法, 如非精确的量化形式或者是含糊不清的语言等。 b. 采取适当的形式描述与表达模糊信息, 如隶属度函数、可能性分布函数, 以线性或非线性形式来描述模糊信息, 在这个过程中, 应该充分反映决策者的意愿和观点, 即主观性或偏爱。 c. 在 a和b的基础上, 根据问题的特点和要求, 采用适当的数学工具和方法, 建立模糊优化模型。

建立模糊规划模型的方法有两种:一种是在对生产调度系统充分了解之后, 先建立一个清晰规划模型, 然后根据各变量或参数以及约束的实际意义, 确定具有模糊性的因素, 选取合适的模糊表示方式, 从而建立一个模糊规划调度模型;另一种是先确定需要模糊化的变量或参数, 根据调度系统的实际状况直接建立模糊约束和模糊目标。文献[7,10]结合模糊理论, 建立起了生产调度的模糊线性规划模型。这类模型可以用模糊数学的方法求解[11], 目前已有多种求解方法, 例如, 容差法[10]、区间分析[12]等。

1993年Kondili以STN为工具, 提出了基于间歇化工过程的静态调度模型MILP, 成为生产过程的静态调度模型的典范。此后生产调度人员在此模型基础上做了不少研究和改进。

采用数学规划的建模方法, 表达清晰, 易于在计算机上求解, 但生产环境具有很多不确定性因素, 存在建摸不确定性和求解空间太大, 造成计算困难, 特别是不能反映特定调度领域的自然结构, 所以很难应用经验知识去处理调度问题。文献[13]对此做了尝试, 并取得了较好的效果。

《2.2参数辨识型 (parameter identification) 》

2.2参数辨识型 (parameter identification)

基于数据的建模 (data-driven modeling) 是从系统的输入输出数据来产生规则库 (通常是IF—THEN规则) , 进行参数辨识, 从而获得模糊推理模型。一般用于对非线性系统的建模。最常用的是T-S模糊模型[14]。

模糊建模通常分两步。第一步是产生描述系统的一个近似模糊模型, 隐含的是确定必要的规则数M。这一步的输出可被看作是最终规则库的总规则。第二步是调整最初的粗糙规则来确定最终规则库[15]。对模糊逻辑规则的参数的辨识问题, 现在大多融合进智能算法[16,17,18]。

《2.2.1 模糊专家系统》

2.2.1 模糊专家系统

近年来, 过程工程领域出现了一个重要的趋势, 充分利用非数值化的信息, 如专家经验和经验规则等, 对难以精确模拟的过程系统建模和优化控制, 出现了专家系统、人工神经网络等研究方向。

模糊专家系统是一类在知识的获取、表示和运用过程中全部或部分采用了模糊技术 (使用模糊集和模糊逻辑来表示和处理知识的不确定性和不精确性) 的专家系统的总称。就专家系统的结构 (即组成部分) 和设计方法而言, 模糊专家系统与传统专家系统是类似的, 模糊专家系统需要解决的主要是两个问题:模糊知识表示和模糊推理方法。

开发模糊专家系统可以适应自动知识获取及经验总结的需要, 能较好地表达和处理人类知识中固有的不确定性, 适于进行自然语言处理, 从而可建立起对用户友好的人-机界面; 而且, 采用模糊规则和模糊推理方法来表达和处理专业领域中的知识还可以有效地减少知识库中规则数量, 增加知识运用的灵活性和适应性。

与传统专家系统相比, 模糊专家系统的知识表示能力获得了极大的提高。对知识表示而言, 由于使用了语言变量, 它的值可以由上下文相关的模糊集来定义, 而模糊集的含义可用各种不同的隶属函数来表示, 这些隶属函数的值是由领域专家给出的主观判断。模糊集为这类不确定知识的表示提供了一个有力的武器。一个实用的基于规则的模糊专家系统通常包括6部分:输入输出模块, 模糊数据库, 模糊知识库, 模糊推理机, 学习模块和解释模块。文献[19]提出一种用于性能评价和故障测试的模糊专家系统, 而文献[20]针对纺织工业生产系统建立了一个关于调度的模糊专家系统, 用来描述计划决策。

现在的专家系统一般都是针对具体的生产过程, 没有有效的针对整体的总体模型。知识库的动态性及规则自学习也需要完善, 所以模糊专家系统的开发还有待进一步的研究。

《2.2.2 粗糙集方法和模糊聚类方法》

2.2.2 粗糙集方法和模糊聚类方法

在实际问题中经常需要分类, 粗糙集理论和模糊聚类理论都是分类的有效手段。它们对T-S模型的辨识, 就是利用上述分类技术来确定系统的模糊空间和模糊规则数, 然后再采用有效的方法进行辨识。它通常应用于对生产调度过程中输入数据的精简与分类, 以此作为模糊规则的输入数据, 并结合其他智能与非智能方法进行进一步的分析与求解。

1982年由波兰数学家Pawlak首次提出的粗糙集 (Rough set) 理论是一种新型的处理模糊和不确定知识的数学工具[21]。经过十几年的研究与发展, 它已经在人工智能、知识发现、模式识别与分类、故障检测等方面得到了较为成功的应用。与模糊集合需要指定隶属度函数不同, 粗糙集的隶属度函数是客观计算的, 只与已知数据有关, 从而避免了主观因素的影响。文献[22]采用了粗集神经专家系统进行知识处理和决策选择。把模糊集理论与粗糙集理论结合起来的模糊粗糙方法、粗糙模糊方法, 已在理论与应用中有了一定的发展。

聚类分析是数理统计中研究物以类聚的一种多元分析方法, 即把一组个体按照相似性归成若干类别, 有着广泛的应用。它的目的是使得属于同一类别的个体之间的距离尽可能小, 而不同类别上的个体间的距离尽可能大。模糊聚类是应用最为广泛的一种聚类模型, 它是利用模糊等价关系将给定对象分为一些等价类, 是一种公认的获取初始模糊模型的方法, 各种模糊C-均值法被广泛应用, 比如FCM算法[23]。其仿真实例表明, 采用带有有效准则的聚类技术能够获得好的初始值, 使得计算加快, 能获得满意的结果。模糊聚类还常和其他决策方法结合起来用于多目标决策分析中, 比如基于遗传算法的模糊聚类[24]。文献[25]使用模糊聚类将运输任务在不同水平上分类, 对一个运输系统进行最优调度。

然而FCM算法是一种基于全局比较的聚类, 它需要考察所有的个体才能决定类的划分;因此它要求所有的数据必须预先给定, 而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度, 难以适用于数据库非常大的情况。

《2.2.3 模糊神经网络》

2.2.3 模糊神经网络

随着模糊理论和神经网络技术研究的进一步发展, 将模糊理论和神经网络技术有机地结合起来, 使之相互取长补短, 充分发挥各自的优势, 提高整个系统的表达能力和自学习能力已成为当前的一个研究热点。

神经网络生产调度模型是用不同类型的单元网络表示不同类型的约束条件, 然后通过适当连接这些单元神经网络, 得到资源约束和排序约束的网络表示, 实现生产调度的建模。

模糊理论和神经网络技术相结合的内容十分丰富, 拓扑结构和自学习算法也层出不穷。文献[26]研究了模糊神经网络对于复杂系统的模糊建模与控制。以往的模糊系统, 其输入多是人为划定的。为了达到精度要求, 常需要对每个变量划分较多的区间, 当维数 (输入变量) 较多时, 模糊输入划分子空间将成指数增长。文献[23]提出, 首先利用模糊聚类技术来确定系统的模糊空间和模糊规则数, 然后利用模糊神经网络来调整模型的前件参数和后件参数。

神经-模糊的方法给解决实际动态调度问题提供了一个有效的办法。文献[27]设计了一个动态自适应的基于模糊规则的控制器, 用于一个shop调度系统, 即基于神经-模糊规则的分配系统。神经网络的学习机制用于调整模糊控制器的参数, 而控制器的误差使用改进的梯度方法最小化, 使得系统收敛到给定规则的最可能好的状态。

但利用模糊神经网络建模依赖于输入数据的代表性以及模糊规则的代表性和完整性 (即能表征所有实际应存在的模糊规则) , 并且同样存在神经网络所具有的不足:比如其学习是在现有的知识基础上, 网络越大, 学习越困难;仍具有易于陷入局部最优的缺点, 网络权值不明确等。

《2.2.4 模糊Agent理论》

2.2.4 模糊Agent理论

Agent技术被认为是进行分布式工业系统建模的一种重要方法, 是设计与实施分布式智能制造环境的最自然的手段[28]。Agent是一个运行于动态环境中的具有较高自治能力的实体, 其根本目标是接受另一个实体的委托并为之提供帮助或服务, 能够在目标任务的驱动下主动采取包括学习、通信、社交等各种手段感知、适应其外在环境的动态变化并作出适当的反应。基于Agent的作业车间调度是最符合智能制造机理的一种调度模式, 具有广阔的应用前景。

在作业车间的调度规则中, 常常包含着人的经验和知识, 这些经验知识常常具有模糊性。调度专家可以用模糊的、直觉的调度知识获得满意的调度结果, 因此有必要将这种模糊推理过程融入到调度决策中。把模糊逻辑用于车间调度并不是一个新技术。但是普通的模糊调度方法都有同样的缺点, 即这些方法所考虑的系统动态变化因素主要是系统的内部状态与参数, 如设备负荷情况、零件加工时间、在制品状况等, 没有考虑系统结构的变化, 如系统中某些设备发生故障和系统环境变化 (如原料供应情况的变化) 等因素, 因而系统的适应能力是有限的。而将多Agent技术与模糊逻辑结合起来, 由于一个资源Agent本身就代表一台设备, 所以Agent之间的互相协调能够有效地反映作业车间的实际运行环境, 这样可以有效地避免上述不足。

Agent调度决策的知识模型是实现作业车间模糊调度决策的第一步。实现这一步的关键是要解决以带有模糊词句的自然语言所描述知识在计算机中存取和使用的问题。这意味着必须对这种以模糊的自然语言形式表达的知识进行严谨的数学描述。文献[29]应用模糊集理论和方法, 对基于合同网的调度算法作了改进, 形成了新的基于多Agent的模糊调度方法。文献[30]建立了适用于解决病态结构问题的大规模的多Agent模糊决策支持系统。

采用模糊集理论, 研究多智能体系统中各智能体的不一致性和不确定性, 探讨多智能体可信度、协调模型及在复杂环境下智能体间的学习与协作, 这是目前有待于研究的方向。

《2.2.5 模糊Petri建模》

2.2.5 模糊Petri建模

Petri网作为一种建模工具, 适合于许多应用领域。针对Petri的特性, 抓住模糊性这个特性, 建立基于模糊产生式规则的模糊Petri网模型[31], 能较好地表示和处理这些模糊知识。

模糊Petri网由库所和变迁组成, 它将模糊产生式规则中的前提和结论都看作是一种位置, 而前提与结论之间的关系看作为一种变换。文献[32]中提出一种用于故障诊断的动态模糊Petri网模型, 能根据变迁的可信度大小, 采用深度优先的搜索方法, 以反向并行推理来缩小搜索空间, 寻找到一条最有可能产生已知故障的路径。并且可以对诊断知识的不确定性、冗余性等进行校验, 部分地实现了自学习功能。

模糊Petri网建模虽然比较直观, 但很难用传统的数学方法进行求解;而且当规模较大时, 其直观性也大大降低。针对这些不足, 利用改进的模糊Petri网对复杂系统进行建模, 成为一个热门话题。

《2.2.6 算法模糊建模》

2.2.6 算法模糊建模

遗传算法是基于自然选择和基因遗传学原理的随机搜索算法。它将适者生存这一基本的进化理论引入串结构, 使用复制、交叉和变异等基因操作, 在串之间进行有组织但又随机的信息交换。伴随着算法的运行, 优良的品质被逐渐不断地继承下来, 坏的特性被逐渐淘汰。运用遗传算法求解问题, 首先需将所要求解的问题表示成编码串, 然后进行基本的操作:选择、交叉、变异。遗传算法的特点:并行性, 全局寻优。

模糊建模是建立描述待辨识对象输入输出变量的模糊映射关系的模糊规则组。一组模糊规则可看作一种关于输入输出模糊度的排列组合, 模糊建模是寻找最佳的输入输出模糊度的排列组合。遗传算法作为一种有效的组合优化技术已开始应用于模糊建模。基于遗传算法的模糊建模需要解决的关键技术包括模糊规则的串表达、遗传操作算子、所生成的模糊规则的优劣度评价。

对于一个经遗传操作算子得到的二进制串可转换为一组模糊规则。根据该组模糊规则和五层前向网络组成的模糊神经网络结构, 通过模糊化、模糊规则推理、去模糊化可计算出不同输入时模糊模型的输出。这样根据一系列输入与期望输出的训练样本可计算出模糊模型输出与期望输出间的误差累积, 从而评价该组模糊规则的优劣[25]。这种方法依赖于一系列输入与期望输出的训练样本。训练样本应具有好的分布性 (反映模糊模型可能的不同输入情况) 、代表性 (反映模糊模型可能的各种典型输入情况) 。遗传算法的适应函数较难选取, 处理实际问题时有时不能满足实时性和调度效果的要求。

《2.2.7 混杂模糊建模》

2.2.7 混杂模糊建模

过程建模是过程系统的控制、诊断、优化中最重要的步骤[14]。混杂Fuzzy-first原理模型适用于不能得到一个完全的物理模型的情况[33]。大多数情况下, 由于很难获得First principal 模型, 所以从数据中创建模型。文献[33]提出一种结合专家经验、局部线性模型和历史数据来统一构建一个混杂灰箱模糊模型, 它包括两层:第一层包括从语言信息创建的专家模糊模型、局部线性模型、从数据创建的T-S模糊模型;第二层是决策模块, 用来确定使用第一层的哪种模型。 第二层的输出就是混杂模型的输出。由于语言信息的帮助, 传统模糊模型因为稀少的训练数据造成的外推能力问题可被解决。这种方法建模较准确, 较好的接近实际模型, 但同时使得难度加大, 求解费时, 对大型模型不太适用。

由于上述两大模糊建模方法各自的局限性, 将模糊理论与各种算法 (如神经网络、模糊树、加速进化规划等) 的结合成为当前研究的重点与热点。基于模糊着色Petri网, 基于遗传算法的模糊树方法[34], 基于粗集理论的模糊神经网络建模方法研究及混杂方法等就是这些应用的范例, 并且各种方法的结合[35,36]层出不穷。

《3 模糊建模展望》

3 模糊建模展望

1) 组合调度模糊建模

虽然组合调度模糊算法现在正方兴未艾, 但仍然存在很多问题。如何更加合理、有效地利用各种算法的优点, 相互弥补各自的缺点, 以便在一定程度上解决组合爆炸的问题, 将需要更深层次的研究。

2) 系统工程方法模糊建模

近年来发展起来的新兴学科——系统工程, 是一门跨越许多学科的科学, 而且是填补这些学科边界空白的一种边缘学科。系统工程的理论基础包括系统论、信息论、控制论、运筹学等学科技术。系统工程的一般概念和它的基本理论及模糊数学恰好弥补了这一不足, 为调度决策的发展开拓了一个新方向[37]。利用系统工程理论与模糊理论的结合来建模或者精简模型, 将会成为一个较好的建模方法。

3) 算法建模

将模糊集理论与进化计算结合起来, 建立适合不确定动态环境的进化计算理论体系和相应算法, 使进化计算在遗传和进化的同时具备自组织和自学习的能力, 并且用于对模型的建立及动态调整。

《4) 模糊Agent理论建模》

4) 模糊Agent理论建模

智能体理论研究十分重视跨学科之间的横向联系与交叉综合, 并具有相当大的难度与挑战性, 它所涉及的知识面极为广泛。Agent的将来, 是一个具有社会性的自组织的协作体系 (Multi-agent) , 对生产调度系统可能产生深远影响。利用Agent的调度系统的模糊建模, 势必会引起调度领域的大变革。