学位论文 > 优秀研究生学位论文题录展示

自动制造系统的Petri网控制器设计及优化

作　者: 胡核算
导　师: 李志武；周孟初
学　校: 西安电子科技大学
专　业: 机械电子工程
关键词: 自动制造系统离散事件系统资源分配系统死锁预防活性监督控制比例监督控制数学规划 Petri网信标
分类号: TP273
类　型: 博士论文
年　份: 2010年
下　载: 330次
引　用: 1次
阅　读: 论文下载

内容摘要

传统的批量制造系统已难以应对激烈的市场竞争和快速的需求变化,柔性自动制造系统应运而生。对此类系统的分析与控制因而成为生产系统领域中的研究热点问题。本学位论文主要围绕着题为“基于Petri网的自动制造系统死锁分析与控制研究(60474018)”和“Petri网的基本信标理论(60773001)”等两项国家自然科学基金项目的研究任务,对自动制造系统监督控制中的相关理论和技术展开研究。本学位论文同时也受到“教育部归国海外学者实验室基金(030401)”,“教育部归国海外学者研究基金(2004-527)”的资助以及国家863计划项目“多重生命周期绿色电子产品设计(2008AA04Z109)”。本学位论文致力于解决关乎我国国计民生的制造业中的关键技术性瓶颈问题。众所周知,先进的制造产业的核心竞争力来自于先进的制造系统。因此,制造系统,特别是以半导体制造系统为代表的现代制造系统在目前乃至可以预见的20至30年内,为我国国民经济的可持续发展提供着有力的支撑和保障,同时也是我国综合国力的一个重要表现。以计算机为核心的信息技术在制造系统中的广泛应用,正使得越来越多的机械化制造系统演变为自动化制造系统,刚性制造系统演变为柔性制造系统。因此,现代制造系统越来越明显地表现为一种复杂的大系统,具有多目标、多约束、动态和强离散性。自20世纪90年代以来的20年时间里,如何实现对这些系统的行之有效的分析和控制成为控制理论领域具有挑战性的科学问题,同时也是工业界亟待解决的关键技术问题。值得注意的是,北美洲的美国和加拿大,欧洲的德国、法国、意大利和西班牙,亚洲的日本、韩国和台湾等许多工业化发达国家和地区的科学家都对该领域表现了极大的研究热情。有资料表明,一条普通规模的半导体生产线的自动化水平每提高一个百分点,其在一年内所增加的利润将以千万美元为单位进行计算。自动制造系统是一种典型的资源分配系统,其中的资源包括加工中心、机器人、传送带等。这类系统根据预先设定的工艺路线并行地加工与处理原料及半成品。这些并行加工过程对有限资源的竞争会导致死锁。因此,需要一定的机制将资源合理地分配给各个过程。这种分配机制应该使得系统在无死锁的前提下保证一定的性能。绝大多数的自动制造系统都属于离散事件动态系统,因此具有事件驱动特性,在时间和空间上的运动轨迹都是离散的,同时也具有异步、并发和不确定性的特点。Petri网由于具有简约和规范的表述形式,在制造系统中的建模、分析和控制中得到了很大应用和发展。就其在离散事件系统中的作用和意义而言,Petri网与连续系统中的微分方程及差分方程对等。本学位论文的研究课题关注于应用Petri网理论实现自动制造系统中的无死锁性分析和控制。该课题的研究无论对于自动制造系统还是Petri网理论本身都具有重大的理论和应用价值,同时也极具挑战性。自动制造系统中的无死锁性可以类比于连续系统中的稳定性,无论一个制造系统性能多么优秀,死锁都是不可以接受的,因为这意味着系统随时可能出现生产停滞现象,从而造成严重的甚至灾难性的后果。本学位论文在诸多方面取得了一系列开拓性、前沿性的研究成果,简要列举如下:第一部分,根据基本信标对应于一组线性无关向量组的原理,首次提出了基本信标不唯一的思想。控制基本信标即可以实现对目标系统的控制,可以起到简化控制器结构的目的。但是控制不同的基本信标,受控系统的可达状态数目可能相差很远。因此,基本信标不唯一的思想可以启发我们去进一步地寻找可以使得受控系统可达状态数最多的一组基本信标。这一点无论在控制理论上还是在工业实践中都具有重要意义。本论文首次提出了最优基本信标的概念。但是,这种过于简单的关于最优基本信标的描述仅仅具有理论意义,因为实际中可达状态数是难以实现遍历的。本学位论文的研究发现了当一组基本信标,与之相对应的从属信标全部是严格从属信标时可以使得受控系统实现最多的状态数。从而使得最优基本信标的计算具有现实可行性。并进而提出了可以高效地计算最优基本信标的代数算法。本学位论文的研究表明当一个信标不能被除自身之外的所有的信标线性表示时,该信标必然是最优基本信标而不可能是从属信标。该研究成果将原本需要组合优化才能解决的计算问题转化为简单的线性规划问题,从而实现了最优基本信标计算的高效性。现有关于基本信标的研究拘泥于普通网系统,不完全适合于复杂自动制造系统的分析与控制。本论文的研究进一步地将基本信标的研究推广至一般网系统。该方法充分考虑了现实中自动制造系统资源分配的具体特点,应用非充分标识的信标而不是可清空的信标的概念,在一般意义上描述了更加复杂和实际的系统中的死锁产生机理。从而将死锁预防机制从简单的代数限制条件转化为加权的代数限制条件。与现有的方法相比,本论文提出的方法可以极大地降低控制的复杂度,提高受控系统的性能,而且计算简单,并为后续的研究提供了理论基础。另外,本学位论文中的研究也可以成功应用于其他资源分配系统,充分显示了其坚实的理论基础和广泛的应用前景。本部分研究成果主要发表在IEEE Transactions on Systems, Man, and Cybernetics - Part C:Applications and Reviews, 2007, IEEE Transactions on Automation Science and Engineering,2009和IEEE Transactions on Multimedia, 2009。第二部分,根据Petri网的不变式特性,提出了自动制造系统中的死锁控制与比例控制问题及其解决机制。前者要求避免因死锁而导致的工件加工进程停滞现象,后者则需要引入合理的调节机制使得特定的工件按照预先设定的比例进行加工。若不考虑不变式特性,此类研究需要借助自动制造系统的可达状态图,从中确定关键的加工路径、加工状态和加工事件。为实现死锁控制,需要对关键的加工状态下的加工事件设定不同的优先级别,使有可能导致死锁的事件具有较低的优先级别。为实现比例控制,需要对特定的事件设定理想的发生概率。显然,无论优先级别或者发生概率都无法完全避免死锁状态的出现或者确保预定比例控制的实现。另外,复杂系统中的不确定行为也有可能使得实际的优先级别和发生概率远离它们的预定值。另外,在同一系统中,优先级别和发生概率的统一协调往往是极其富有挑战性的,有时甚至完全不可能实现。本学位论文根据Petri网的不变式原理,使用监督控制库所实现了上述两种控制策略的综合。为了较好地解决此类问题,本学位论文提出了两类新的Petri网子类,分别适用于具有柔性加工路径和具有装配操作的自动制造系统的研究。在每个加工阶段,两类Petri网都允许多个资源的获取,使得研究结果更具有理论和应用意义。本论文证明了,应用不变式的比例控制不会引入新的信标,也就是它们自身不会导致系统的死锁。这就意味着这两种不同的监督控制器可以独立地进行设计与实现。本论文提出了一组线性不等式,从而可以迭代计算Petri网中的信标,实现了可以高效计算的控制器设计算法。该算法有效地实现了将原本需要进行算法复杂度为指数增长的枚举运算才能实现的死锁状态检测方法转化为简单的数学规划问题,无需计算出所有的状态或信标即可甄别出死锁状态及其对应的信标,并对它们加以控制。同时,由于数学规划模型也很好地解释了死锁状态与非充分标识信标之间的关系,为更加有效的死锁控制策略的提出提供了理论依据。本部分研究成果主要发表在IEEE Transactions onSystems, Man, and Cybernetics - Part A: Systems and Humans, 2010。另外也有相关成果将发表在IEEE Transactions on Industrial Informatics, 2010。第三部分,针对考虑资源分配的自动制造系统,提出了兼顾控制器实现代价和受控系统性能的活性监督控制器设计策略。在实际的自动制造系统中,控制器由观测和控制单元组成,这对应于应用Petri网实现的控制库所的输入和输出弧。具体地,一个控制器应该由传感器和执行器来实现。不难想象,过多的或设计不合理的传感器和执行器必然增加系统的结构复杂性,提高系统实现成本,加大系统故障概率。现有研究没有考虑这些控制器的实现代价问题,同时也缺乏定量地分析这些控制器对受控系统性能的影响。这往往导致较高的实现代价、较强的控制约束和较低的受控系统运行效率。应用数学规划方法,本学位论文给出了一种可以计算实现代价最小的监督控制器的方法,节约了系统的控制成本。在此基础上,本学位论文将研究成果进一步地应用于时间Petri网,以便于综合评价系统的控制代价和运行效率。这两者被证明在很多场合是相互矛盾的。在很多情况下,如果要降低控制器的实现代价,就必须牺牲系统的性能;如果要提高系统的性能,就必须承受较高的控制器实现代价。论文应用权系数法实现了综合评价多个目标的数学规划方法,进而提出了降低控制器实现代价和提高系统性能的新方法,文中提出的方法可以用来取得控制器实现代价和系统生产效率的平衡。在本学位论文中,Petri网中每个变迁被赋予一个观测代价和控制代价,分别对应相应位置的传感器和控制器的实现成本,应用数学规划方法可以有效地确定综合实现代价最小的控制器。该研究成果分别应用于具有柔性加工路径和具有装配操作的自动制造系统,证明了其有效性和高效性。为了取得控制器的实现代价和受控系统生产率之间的平衡,在本研究中,库所或者变迁被进一步地赋予时间信息以便于评估各个加工阶段和事件的效率问题,并进而提出了考虑时间因素的新的Petri网子类。本论文研究结果表明,对于需做装配操作的系统,时间信息本身不会导致死锁,因此应用数学规划方法可设计出实现代价低而控制效率高的控制器。但是对于具有柔性加工路径的系统,时间信息加上不同加工路径可以导致死锁,因此在设计控制器之前,需要有相应的预处理。为此,本学位论文的研究表明应用比例控制器可以有效地消除各个加工路径中因为时间因素而可能出现的死锁现象。本部分研究成果主要发表在IEEE Transactions on Automation Science and Engineering, 2010。另外也有相关成果已分别递交给IEEE Transactions on Automation Science and Engineering和IEEE Transactionson Automatic Control等杂志评审。第四部分,针对考虑全局时间的自动制造系统,提出了具有多项式时间复杂度的监督控制器设计策略。自动制造系统作为一种客观存在,其运行总是和时间相关的。因此,时间尺度具有重要意义,应该和系统的模型相结合。相应的,许多控制约束应该是时间性的而不仅仅是代数或逻辑性的。关于这方面,现有的研究总是应用基于自动机的监督控制理论并结合区域法。已经证明,此类研究问题是NP完全问题。这是因为,无论自动机或者区域法都要求遍历系统的全部运行状态,而系统状态数随系统的规模呈指数增长。本论文的研究显示,实际上,考虑时间的约束问题是可以在多项式时间内解决的。文中的方法应用了一般线性约束。相对于线性标识约束,一般线性约束有着更强的描述约束的能力。通过将一个约束转化为标识、发射向量和Parikh项,控制库所可以应用代数的方法简单计算得到。这就避免了现有研究必须进行的危险状态和事件的分离操作问题。后者不但要求遍历系统的可达状态,而且要求计算可达图中的所有有向回路并为之建立相应的代数方程。即使对于一个中等规模的自动制造系统,这三项操作中的每一项都意味着巨大的存储量和计算量。本学位论文主要关注于全局时间在控制器设计中的影响和作用,提出了考虑全局时间信息的Petri网子类。该网系统由两部分组成,一部分用来描述自动制造系统的逻辑结构,另一部分用来显式地表达全局时间。显然,前者对于后者是可观测可控制的,而后者对于前者是可观测但不可控制的,这是因为时间是不能被停止的。在单纯的逻辑控制中,一个加工事件是否发生取决于是否满足逻辑约束条件。在考虑全局时间信息的情况下,一个加工事件的发生应该同时满足逻辑和时间约束。本论文应用代数方法,在不计算系统可达图的情况下,首次解决了对于考虑时间约束的Petri网控制器的实现问题。由于一般线性约束将系统关联矩阵分解为输入和输出矩阵,因此控制器允许自环的存在,从而有效地解决了在有不可控制事件的情况下,自动制造系统的控制难题。自环的存在使得指向特定不可控制变迁的控制库所输出弧可以不影响该变迁的发射,从而避免将该约束转化为有更强限制的约束的操作,进而有效地确保系统的最大许可行为。本部分研究成果主要发表在IEEE Transactions on Automation Scienceand Engineering, 2010。

全文目录

摘要  5-10
Abstract  10-25
1 Introduction  25-41
  1.1 Overview of Automated Manufacturing Systems (AMS)  26-27
  1.2 Process Routes and Resource Allocation  27-29
  1.3 Deadlock Problems and their Resolution  29-31
  1.4 Background and Literature Review  31-38
  1.5 Thesis Organization  38-41
2 Preliminaries of Petri Nets  41-49
  2.1 Introduction  41
  2.2 Basic Definitions  41-44
  2.3 Structural Invariants  44-45
  2.4 Siphons and Traps  45-46
  2.5 Petri Net Classes  46-47
  2.6 Timed Petri Nets  47-48
  2.7 Summary  48-49
3 Elementary Siphon-Based Iterative Deadlock Resolution  49-69
  3.1 Introduction  49-50
  3.2 Sub-optimal Elementary Siphons in Petri Nets  50-54
  3.3 Enumeration and Control of Sub-optimal Elementary Siphons  54-62
  3.4 Flexibility Enhancement  62-63
  3.5 Experimental Results  63-66
  3.6 Summary  66-69
4 Deadlock Resolution Using General Nets with Sequential Processes  69-87
  4.1 Introduction  69-70
  4.2 Systems of Sequential Systems with Shared Resources  70-72
  4.3 Insu?ciently Marked Siphons  72-75
  4.4 Control of Insu?ciently Marked Siphons  75-80
    4.4.1 Supervisor Synthesis Policy  75-77
    4.4.2 Simplification of Supervisor Structure  77-80
  4.5 An Illustrative Example  80-85
  4.6 Summary  85-87
5 Liveness and Ratio-enforcing Supervision of AMS with Flexible Routes  87-105
  5.1 Introduction  87-88
  5.2 Ratio-enforced AMS and Petri Net Models  88-91
  5.3 Separability of Ratio and Liveness Enforcements  91-92
  5.4 Algebraic Method to Synthesize Liveness-enforcing Supervisor  92-99
    5.4.1 Transformation of S~4R to PT-ordinary nets  93-95
    5.4.2 Algebraic Method to Derive Empty Siphons  95-96
    5.4.3 Supervisor Synthesis  96-99
  5.5 AMS Example  99-104
  5.6 Summary  104-105
6 Liveness and Ratio-enforcing Supervision of AMS with Assembly Operations ..  105-125
  6.1 Introduction  105
  6.2 AMS and Petri Net Models  105-113
    6.2.1 Ratio-enforced Weighted Augmented Marked Graphs  106-111
    6.2.2 Principle of Separation  111-113
  6.3 Iterative Methods for Supervisor Design  113-118
    6.3.1 Detection of Siphons via Mathematical Programming  113-115
    6.3.2 Liveness Enforcement  115-118
  6.4 Illustrative Example  118-124
  6.5 Summary  124-125
7 Supervisor Optimization for Deadlock Resolution in AMS  125-151
  7.1 Introduction  125-126
  7.2 Supervisor Optimization  126-135
    7.2.1 Preliminaries on Supervisory Control Using General Mutual Exclusion Constraints  126-127
    7.2.2 Optimization for Improved Petri Net Monitor Design  127-135
  7.3 Low-cost Supervisor Design for S~4R  135-138
  7.4 Illustrative Example  138-140
  7.5 Performance Evaluation  140-143
  7.6 Extension to Timed S~4R  143-149
    7.6.1 Liveness Analysis of Timed S~4R  143-145
    7.6.2 Computation of Minimum Cycle Time for Timed S~4R  145-147
    7.6.3 Supervisor Design for Timed S~4R  147-149
  7.7 Summary  149-151
8 Low-Cost and High-Performance Supervision for Ratio-Enforced AMS  151-169
  8.1 Introduction  151
  8.2 Timed Ratio-enforced Augmented Marked Graph (TAMG)  151-158
    8.2.1 The class of TAMG Models  152-154
    8.2.2 Liveness Analysis  154-155
    8.2.3 Computation of Minimum Cycle Time  155-158
  8.3 Supervisor Synthesis and Optimization for Liveness Enforcement  158-163
    8.3.1 Liveness Supervision Using General Mutual Exclusion Constraints  158-160
    8.3.2 Supervisor Design Method  160-163
  8.4 Illustrative Example  163-166
  8.5 Summary  166-169
9 Algebraic Synthesis of Timed Supervisor for AMS  169-185
  9.1 Introduction  169
  9.2 System of Sequential Systems with Shared Resources and Global Time (S~4RGT)  169-174
    9.2.1 S~4RGT Models  170-171
    9.2.2 Live S~4RGT  171
    9.2.3 Monitor Design Using the Theory of Regions  171-174
  9.3 Timed General Mutual Exclusion Constraints and their Algebraic Implementation  174-179
  9.4 Illustrative Example  179-182
  9.5 Experimental Results  182-183
  9.6 Summary  183-185
10 Conclusions and Future Research  185-191
  10.1 Contributions  185-188
  10.2 Limitations and Future Research  188-191
Acknowledgements  191-193
References  193-213
Finished Papers  213-221
Honors, Awards, and Professional Activities  221-224

自动制造系统的Petri网控制器设计及优化

内容摘要

全文目录

相似论文