CN109739196B - 含有不可观与不可控事件的自动制造系统无死锁控制方法 - Google Patents

Abstract

本发明属于自动制造系统技术领域，涉及一种含有不可观与不可控事件的自动制造系统无死锁控制方法,至少包括如下步骤：步骤一，生成自动制造系统在线可行步长；步骤二，依据生成自动制造系统在线可行步长获取最优步长；步骤三，依据最优步长进行避免死锁控制。它提出一种含有不可观与不可控事件的自动制造系统无死锁控制方法,以便能在不可控与不可观的情况下实现许可性最大的无死锁控制。

Description

含有不可观与不可控事件的自动制造系统无死锁控制方法

技术领域

本发明属于自动制造系统技术领域，涉及一种含有不可观与不可控事件的自动制造系统无死锁控制方法。

背景技术

在Petri网模型下的自动制造系统中，人们提出了很多死锁预防策略，这些策略被广泛用于解决Petri网中的死锁问题。然而，大部分策略都是在假设所有变迁都可控并且可观的情况下得出。而在实际系统中，不可控和不可观变迁是非常常见的，例如：化学反应，化学反应的在进行的时候过程中有许多不可观与不可控的反应。当存在不可控变迁或不可观变迁时，由现有的针对可观可控的策略得到的控制器可能无法阻止系统进入死锁状态。这是因为控制器无法控制不可控变迁，也无法观测不可观变迁。因此已有的控制策略不能用于处理存在不可控和不可观变迁的系统。所以在为系统设计控制器时必须同时考虑不可控变迁以及不可观变迁的影响。但目前并没有一种普遍适用或者较好的控制方法来对含有不可观与不可控事件的自动制造系统进行控制。

到目前为止，研究者研究了含有不可观与不可控事件的自动制造系统的死锁避免策略，还是存在一些缺陷，具体体现在：1.大部分无死锁控制策略都是在假设所有变迁都可控并且可观的情况下得出，并没有考虑系统中存在不可控与不可观的事件的情况。2.针对含有不可控与不可观事件的自动制造系统的无死锁控制的研究，大部分的控制方法是离线的计算机制，离线的加控制器来进行死锁的避免。3.考虑了自动制造系统中不可观与不可控事件的存在，但控制方法具有保守性，导致系统的许可性没有达到最大。

发明内容

为解决现有研究中存在的问题，本发明的目的是提出一种含有不可观与不可控事件的自动制造系统无死锁控制方法,以便能在不可控与不可观的情况下实现许可性最大的无死锁控制。

为实现上述目的，本发明所采用的技术方案是:一种含有不可观与不可控事件的自动制造系统无死锁控制方法，至少包括如下步骤：

步骤一，生成自动制造系统在线可行步长；

步骤二，依据生成自动制造系统在线可行步长获取最优步长；

步骤三，依据最优步长进行避免死锁控制。

所述的步骤一包括：

步骤1：输入PN的初始状态M₀以及初始步长stepsize，不可观变迁集合T_UO，不可控变迁集合T_UC；

步骤2：初始化，令M＝M₀，stepsize＝1，给一个时间T₀；

步骤3：从当前状态M(可能是一个状态也可能是多个状态的集合)，以步长stepsize预测，得到M下可以使能的变迁集合T_en及预测到的可达状态集合Q；

步骤4：将Q中不可观变迁相连的连续的状态划为一类，称这类状态集合为Q_uo；

步骤5：若在M下

则根据步骤4得到含有状态M的Q_uo，更新当前状态M，即令M＝Q_uo，回到步骤3重新向下执行；

步骤6：若M不是Q_uo，根据T_en是否为空，决定回到2重新执行还是继续执行到达新的状态；

步骤7：若M是Q_uo，根据Q_uo中状态是否有可以使能的变迁，决定回到2重新执行还是执行步骤6中部分内容；

步骤8：若程序运行的时间T<T₀，更新当前状态M即M＝M^*，回到2重新执行。否则令s_uoucfs＝stepsize，输出令s_uoucfs。

所述步骤6，包括：

6.1，若T_en为

令stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

6.2若T_en不为

考虑M_dead和Q的关系，发射变迁到达新状态；

其中6.2步骤中，包括：

6.2.1

若

且t∈T_en，则随机发射变迁t∈T_en，到达新的状态M^*；

若

且t∈T_en，则随机发射变迁t∈T_uc，到达新的状态M^*；

6.2.2若

根据

是否为空，决定更新步长回到步骤2执行还是发射变迁到达新的状态；

上述6.2.2步骤中，包括：

6.2.2.1若

则stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

6.2.2.2若临界状态集合

包括步骤：

1)若当前状态M∈M_good；

2)若当前状态M∈M_CR；

其中，1)若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

若

且t∈T_en，则随机发射t∈T_uc，到达新的状M^*；

2)若当前状态M∈M_CR：

若

且t∈T_en，则从T_en中将发射到达坏死或者死锁状态的变迁剔除掉的集合中随机选择一个变迁t进行发射，到达新的状态M^*；

若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

所述步骤7，包括步骤：

7.1若Q_uo中有至少一个状态没有可以使能的变迁，则令stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

7.2若Q_uo中每一个状态都有可以使能的变迁，从上述步骤6的2)开始向下执行。

所述的步骤二包括如下步骤：

步骤1：输入PN的初始状态M₀以及初始步长stepsize，不可观变迁集合T_UO，不可控变迁集合T_UC，步骤一的T₀及的输出s_uoucfs；

步骤2：初始化:令M＝M₀，

S₁＝s_uoucfs；

步骤3：若s_uoucfs≤2则S_uop＝S_uofs则输出S_uop，结束；

步骤4：若S_uofs>2则重新计算预测步长，输出S_uop或者回到步骤3；

所述步骤5，根据

的值是否为0，分两种情况讨论如下：

4.1若

则参考步骤一，从初始状态M₀，以步长

预测；

4.2若

则从初始状态M₀，以步长

预测；

其中4.1步骤中：根据系统是否进入死锁，包括如下步骤：

4.1.1如果在T₀时间内一旦系统走到了死锁状态则令

4.1.2如果在T₀时间内，系统没有走入死锁状态，则令

4.1.3输出S_uop，结束；

同样的，4.2步骤中，根据系统是否进入死锁，包括如下步骤：

4.2.1如果在T₀时间内一旦系统走到了死锁状态则令

更新S₀，回到步骤3，重新执行；

4.2.2在T₀时间内系统没有走入死锁状态，则令

更新S₁，回到步骤3，重新执行。

所述的步骤三包括：

步骤1：输入PN的初始状态M₀，不可控变迁集合T_UO，不可控变迁集合T_UC及步骤二的输出S_uop；

步骤2：初始化，令M＝M₀，stepsize＝S_uop；

步骤3：从当前状态M，以步长stepsize预测，得到M下可以使能的变迁集合T_en及预测到的可达状态集合Q；

步骤4：将Q中不可观变迁相连的连续的状态划分为一类，称这类状态集合为Q_uo；

步骤5：若在M下

则根据步骤4得到含有状态M的Q_uo，更新当前状态M，即令M＝Q_uo，回到步骤3重新向下执行；

步骤6：若

选择发射t，到达新的状态M^*；

步骤7：若

对M进行分类讨论，确定发射的t，到达新的状态M^*；

步骤8：更新当前状态M即M＝M^*，回到3重新执行。

所述步骤6，包括：选择发射t和如下步骤：

6.1若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

6.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

所述步骤7，依据

分两种步骤：

7.1若M∈M_good，选择发射t；

7.2若M∈M_CR，选择发射t'；

其中7.1步骤中，根据t变迁发射进行：

7.1.1若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

7.1.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*；

其中7.2步骤中，根据t变迁发射进行：

7.2.1若

且t∈T_en，则从T_en中将发射到达坏死或者死锁状态，或者是到达含有坏死或者死锁状态的Q_uo的变迁剔除掉的集合中随机选择一个变迁t进行发射，到达新的状态M^*；

7.2.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

与现有的技术相比，本发明具有有益的效果为：

1.本发明考虑了自动制造系统中存在不可观与不可控事件的情况。

2.本发明的死锁避免方法不需要检测全局信息，只需要关注当前状态预测的局部信息，避免了穷举所有的状态，从而计算和存储复杂度大大地简化。

3.本发明采用边预测、边控制的实时在线运行方针，不需要提前设计控制器。根据在当前状态下预测到的状态进行分析判断，根据判断的结果及时地反馈给控制器。控制器做出恰当的控制决策，来决定在当前状态下需要发射那个变迁，从而避免在加工过程中出现死锁状态，导致生产线停滞，造成巨大的损失。

4.本发明的方法是根据算法随机发射变迁的性质从而极大地改善系统的许可性，使系统的许可性尽可能的达到最大。

附图说明

图1是S⁴R模型示意图。

具体实施方式

一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：至少包括如下步骤：

步骤一，生成自动制造系统在线可行步长；

步骤二，依据生成自动制造系统在线可行步长获取最优步长；

步骤三，依据最优步长进行避免死锁控制。

所述的步骤一包括如下步骤：

步骤1：输入自动制造生产开始时所有节点信息M₀(这个M₀里面包含的是六台机器和托盘的信息)及从M₀开始工件后续可能进行那几步装载或者卸载，将这个装载和卸载的次数称为步数并记为stepsize；工件向机器(M₁，M₂)的装载是看不见的，因此称我们将这个事件为不可观事件，这里的不可观变迁集合T_UO里面就包含了这一个不可观事件；进程2中工件是否能装载到机器M₅，M₆上是不可控制，我们将这个事件称为不可控事件，这里的不可控变迁集合T_UO里面就包含了这一个不可控事件；

步骤2：初始化：令当前生产过程的信息记为M，刚开始时我们令M＝M₀，在M这个状态下，我们预测后续如果进行一次装载或者卸载我们整个系统将可能到达的状态，因此我们令stepsize＝1，如果进行两次那么stepsize＝2，依次类推。我们给一个时间T₀，这个T₀是用计算机实现模拟这个系统进行的流程，让系统运行的时间；

步骤3：从当前状态M(可能是一个状态也可能是多个状态的集合，因为该系统中有不可观测事件的存在，所以我们有时无法判断当前系统处于哪一个具体的状态)，用步长stepsize预测，我们可以知道在M下有哪些事件(比如工件的装载或卸载)可以发生，我们将这些可以发生的事件集合称为T_en；在stepsize次的装载和卸载这个过程中系统所能到达的所有状态，我们称这个状态集合为Q；

步骤4：将Q中同一个不可观事件相连的系统的状态划分为一类(即不可观事件发生前和发生后系统所处的状态分为一类)，称这类状态集合为Q_uo；

步骤5：若在M下可能发生的事件中包含不可观的事件即

则根据步骤4得到该不可观变迁对应的Q_uo，更新当前状态M，即令M＝Q_uo，回到步骤3重新向下执行；

步骤6：当前的系统所处的状态是可观的即M≠Q_uo；根据T_en是否为空，决定回到2重新执行还是继续执行到达新的状态；

步骤7：若M是Q_uo，根据Q_uo中的状态下是否有可以发生的事件，决定回到2重新执行还是执行步骤6中部分内容；

步骤8：若计算机程序模拟运行的时间T<T₀，更新当前状态M即M＝M^*，回到2重新执行。否则令s_uoucfs＝stepsize，输出s_uoucfs。

所述步骤6，根据在当前状态是否有事件发生即T_en是否为空，进行讨论如下：

6.1若T_en为

令stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

6.2若T_en不为

Q中是否含有死锁状态来判断发生那些事件然后到达新的状态M^*。

其中6.2步骤中，分为以下两种情况讨论：

6.2.1在Q中没有死锁状态即

6.2.1.1若当前可以发生的事件集合T_en中不含有不可控的事件，则按照正常的加工流程走，到达新的状态M^*；

6.2.1.2若当前可以发生的事件集合T_en中含有不可控的事件，则让不可控的事件发生，到达新的状态M^*；

6.2.2若Q中含有死锁状态，则从预测到的死锁状态进行反推，推到在stepsize步系统经历的状态是否存在某些状态不是不可避免的到达死锁的状态，其可以到达其它正常的状态，我们称这样的状态集合为临界状态M_CR，根据

是否为空再做进一步的判断；

上述6.2.2步骤中，包括：

6.2.2.1若

则stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

6.2.2.2若临界状态集合

分以下两种情况执行：

1)若当前状态是系统所处的正常状态；

2)若当前状态是一个临界状态，即系统在下一步有可能进入死锁状态，也有可能依然处于正常运行状态；

其中，1)若在当前状态下，可能发生的事件集合中不含有不可控的事件，则系统正常运行，到达新的状态M^*；可能发生的事件集合中含有不可控的事件，则让不可控的事件发生，系统到达新的状M^*；

2)若在当前状态下，可能发生的事件集合中不含有不可控的事件，则从T_en中将发射到达坏死或者死锁状态的事件剔除掉的集合中随机选择一个变迁t进行发射，到达新的状态M^*；若可能发生的事件集合中含有不可控的事件，则让不可控的事件发生，系统到达新的状M^*。

所述步骤7，根据Q_uo中状态是否有可以使能的变迁，分两种步骤：

7.1若Q_uo中有至少一个状态没有可以使能的变迁，则令stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

7.2若Q_uo中每一个状态都有可以使能的变迁，从上述步骤6.2开始向下执行；

所述的步骤二包括：

步骤1：输入PN的初始状态M₀以及初始步长stepsize，不可观变迁集合T_UO，不可控变迁集合T_UC，步骤一的T₀及步骤一的输出s_uoucfs；

步骤2：初始化:令M＝M₀，

S₁＝s_uoucfs；

步骤3：若s_uoucfs≤2则S_uoucop＝s_uoucfs则输出S_uoicop，结束；

步骤4：若S_uofs>2则重新计算预测步长，输出S_uoucop或者回到步骤3。

所述步骤5，根据

的值是否为0，分两种步骤：

4.1若

则参考算法一，从初始状态M₀，以步长

预测；

4.2若

则从初始状态M₀，以步长

预测；

其中4.1步骤中：根据系统是否进入死锁，有以下几种情况：

4.1.1如果在T₀时间内一旦系统走到了死锁状态则令

4.1.2如果在T₀时间内，系统没有走入死锁状态，则令

4.1.3输出S_uop，结束；

同样的，4.2步骤中，包括：

4.2.1如果在T₀时间内一旦系统走到了死锁状态则令

更新S₀，回到步骤3，重新执行；

4.2.2在T₀时间内系统没有走入死锁状态，则令

更新S₁，回到步骤3，重新执行。

所述的步骤三包括：

步骤1：输入自动制造生产开始时所有节点信息M₀(这个M₀里面包含的是六台机器和托盘的信息)及从M₀开始工件后续可能进行那几步装载或者卸载，将这个装载和卸载的次数称为步数并记为stepsize；工件向机器(M₁，M₂)的装载是看不见的，因此称我们将这个事件为不可观事件，这里的不可观变迁集合T_UO里面就包含了这一个不可观事件；进程2中工件是否能装载到机器M₅，M₆上是不可控制，我们将这个事件称为不可控事件，这里的不可控变迁集合T_UO里面就包含了这一个不可控事件。算法二的输出S_uoucop；

步骤2：初始化:令M＝M₀，stepsize＝S_uoucop；

步骤3：从当前状态M(可能是一个状态也可能是多个状态的集合，因为该系统中有不可观测事件的存在，所以我们有时无法判断当前系统处于哪一个具体的状态)，用步长stepsize预测，我们可以知道在M下有哪些事件(比如工件的装载或卸载)可以发生，我们将这些可以发生的事件集合称为T_en；在stepsize次的装载和卸载这个过程中系统所能到达的所有状态，我们称这个状态集合为Q；

步骤4：将Q中同一个不可观事件相连的系统的状态划分为一类(即不可观事件发生前和发生后系统所处的状态分为一类)，称这类状态集合为Q_uo；

步骤5：若在M下可能发生的事件中包含不可观的事件即

则根据步骤4得到该不可观变迁对应的Q_uo，更新当前状态M，即令M＝Q_uo，回到步骤3重新向下执行；

步骤6：若Q没有死锁状态，则按照正常的加工流程进行，到达新的状态M^*；

步骤7：若Q有死锁状态，则根据当前所处的状态进行判断，然后决定让那个事件发生从而让系统进入一个新的状态M^*；

步骤8：更新当前状态M即M＝M^*，回到3重新执行；

所述步骤6，选择发射t，包括步骤：

6.1若在系统当前状态下，可以发生的事件集合中不含有不可控的事件则按照正常的流程走，到达新的状态M^*；

6.2若在系统当前状态下，可以发生的事件集合中含有不可控的事件则可以让不可控的事件发生，到达新的状态M^*；

所述步骤7，根据Q中是否含有死锁状态分两种步骤：

7.1若当前系统所处的状态是一个正常运转的状态，我们也称这种状态为好状态，下来需要发生哪一个事件需遵循一定规则；

7.2若当前系统所处的状态是一个临界状态，下来需要发生哪一个事件需遵循一定规则；

其中7.1步骤中：

7.1.1在系统当前状态下，可以发生的事件集合中不含有不可控的事件则按照正常的流程走，到达新的状态M^*；

7.1.2在系统当前状态下，可以发生的事件集合中含有不可控的事件则可以让不可控的事件发生，到达新的状态M^*；

其中7.2步骤中，根据t变迁发射规则如下：

7.2.1在系统当前状态下，则从T_en中将发射到达坏死或者死锁状态，或者是到达含有坏死或者死锁状态的Q_uo的变迁剔除掉的集合中随机选择一个事件让其发生，到达新的状态M^*；

7.2.2在系统当前状态下，可以发生的事件集合中含有不可控的事件则可以让不可控的事件发生，到达新的状态M^*。

本发明中的符号说明：

PN Petri网

stepsize 预测步长

S_fs 可行步长

M₀ 初始状态

M 当前状态

T_en 在M下可以使能的变迁集合

M_dead 死锁状态

Q 在M下以stepsize预测到的所有状态

M_CR 临界状态集合

T_UO 不可观变迁集合

T_UC 不可控变迁集合；

T_uc 在当前状态M可以使能的不可控的变迁集合

T₀ 由系统本身决定

T 实现算法的程序运行的时间

t 变迁

t_uo 不可观的变迁

S_uoucfs 含有不可观与不可控事件的自动制造系统可行步长

S_uop 含有不可观与不可控事件的自动制造系统最优步长

本发明的说明和定义1：

一个Petri网(结构)N是一个四原组(P,T,F,W)，P和T分别称为库所和变迁的集合，P和T非空、有限且不相交。也就是说，

称为流关系或有向弧的集合。W：(P×T)∪(T×P)→N是一个映射，该映射为每一条弧分配一个权值，即W(f)>0若f∈F，则W(f)＝0若

称W为Petri网N的权函数。

定义2：标识(状态)PN为一5要元：

PN＝{PNS，m}

此处：

(1)PNS＝{P，T，F，W}为PN结构，它由定义1确定。

(2)m:P→N为标识PN的标识，它为一列向量，其第i个元素表示，第i个库所中的托肯的数目。特别地，m₀为初始标识，表示系统的初始状态。

定义3：不可控变迁与不可观变迁

(1)不可控变迁：系统在运行的时候我们不能人为的控制变迁是否发射，变迁想发射就发射了，不想发射就不发射，我们控制不住。这样的变迁我们称为不可控变迁。反之，我们可以人为控制变迁的发射，这类变迁称为可控变迁。

(2)不可观变迁：变迁是否发射我们是不知道的，因此我们不能判断我们是处在当前状态还是发射了不可观变迁到达的下一个状态。

实施例说明：

一生产单元由6台机器(M₁，M₂，M₃，M₄，M₅，M₆)进行工件的加工，其中机器M₁，M₂的功能一样，M₃，M₄的功能一样，M₅，M₆的功能一样。一输入传送带传送载有工件的托盘(1个托盘上仅载有1个工件)，工件自动被装载(当然也可人工控制不让其装载，稍后进行装载)到机器上进行加工，加工完成后进行自动传输给下一类机器然后进行后续的加工。为了提高生产的效率，该加工分成两个进程进行加工，第一个进程共有8个托盘可以使用，工件安装在其中之一上，先后由机器人(M₁，M₂)，(M₃，M₄)，(M₅，M₆)依次进行加工。加工完毕后，托盘与成品自动脱离，然后转载新的工件，再回到输入传输带上，但在这个进程中，工件向机器(M₁，M₂)的装载是看不见的，也就是将工件放在托以后我们就不知道工件装载没装载到机器(M₁，M₂)上，是否正在加工。进程2同样也有8个托盘可以使用，工件安装在其中之一上先后由机器人(M₅，M₆)，(M₃，M₄)，(M₁，M₂)依次进行加工。加工完毕后，托盘与成品自动脱离，然后转载新的工件，再回到输入传输带上。但是在两个进程中的不断加工中，有可能导致进程1需要机器M₅，M₆进行工件的加工而被进程2的工件加工所占用，而进程2需要M₁，M₂而被进程1所占用，从而导致两个进程都停止最终导致生产线崩掉。

为了解决这种问题我们可以给以上问题建立系统的PN模型，如图1所示：

(1)首先确定系统的所有资源：该系统资源包括：16个装载工件的托盘、两个进程，每个进程各8个、机器M₁，M₂，M₃，M₄，M₅，M₆。

(2)确定与各资源有关所有活动(操作)及其先后顺序并建立其子模型：

(a)装载工件的托盘经历以下状态与活动：

进程1:

·装载到机器M₁，M₂；

·其上的工件被M₁，M₂加工；

·装载到机器M₃，M₄；

·其上的工件被M₃，M₄加工；

·装载到机器M₅，M₆；

·其上的工件被M₅，M₆加工；

·加工完毕工件从M₅，M₆进行卸载。

用p₁带表载有工件的托盘可使用(若其中含有托肯，表示可用)；p₂，p₃，p₄分别表示托盘上的工件在被机器p₉(M₁，M₂)，机器p₁₀(M₃，M₄)，机器p₁₁(M₅，M₆)加工之中；t₁，t₂，t₃分别表示向机器(M₁，M₂)，(M₃，M₄)，(M₅，M₆)中装载工件，令t₁为不可观变迁，t₄表示从机器(M₅，M₆)中卸载工件。

(b)机器M₁，M₂，M₃，M₄，M₅，M₆经历以下活动和状态：

·工件被M₁/M₂(由p₉表示)加工；

·工件被M₃/M₄(由p₁₀表示)加工；

·工件被M₅/M₆(由p₁₁表示)加工；

·工件从M₅/M₆卸载(由t₄表示)。

进程2的模型简化和上面进程1类似，有一点不同的是进程2的t₅是不可控的，也就是说进程2工件是否能装载到机器M₅，M₆上是不可控制的，有可能能装载上，有可能不能装载上。

Claims (5)

1.一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：至少包括如下步骤：

步骤一，生成自动制造系统在线可行步长；

步骤二，依据生成自动制造系统在线可行步长获取最优步长；

步骤三，依据最优步长进行避免死锁控制；

所述的步骤一包括如下步骤：

步骤1：输入自动制造生产开始时所有节点信息M₀，这个M₀里面包含的是六台机器和托盘的信息及从M₀开始工件后续可能进行那几步装载或者卸载，将这个装载和卸载的次数称为步数并记为stepsize；工件向机器M₁，M₂的装载是看不见的，将这个事件为不可观事件，这里的不可观变迁集合T_UO里面就包含了这一个不可观事件；进程2中工件是否能装载到机器M₅，M₆上是不可控制，将这个事件称为不可控事件，这里的不可控变迁集合T_UC里面就包含了这一个不可控事件；

步骤2：初始化：令当前生产过程的信息记为M，刚开始时令M＝M₀，在M这个状态下，预测后续如果进行一次装载或者卸载整个系统将可能到达的状态，因此令stepsize＝1，如果进行两次那么stepsize＝2，依次类推；给一个时间T₀，这个T₀是用计算机实现模拟这个系统进行的流程，让系统运行的时间；

步骤3：从当前状态M用步长stepsize预测，在M下有工件的装载或卸载发生，将这些发生的事件集合称为T_en；在stepsize次的装载和卸载这个过程中系统所能到达的所有状态，称这个状态集合为Q；

步骤4：将Q中同一个不可观事件相连的系统的状态划分为一类，即不可观事件发生前和发生后系统所处的状态分为一类，称这类状态集合为Q_uo；

步骤5：若在M下可能发生的事件中包含不可观的事件即

则根据步骤4得到该不可观变迁对应的Q_uo，更新当前状态M，即令M=Q_uo，回到步骤3重新向下执行；

步骤6：当前的系统所处的状态是可观的即M≠Q_uo；根据T_en是否为空，决定回到2重新执行还是继续执行到达新的状态；

步骤7：若M是Q_uo，根据Q_uo中的状态下是否有可以发生的事件，决定回到2重新执行还是执行步骤6中部分内容；

步骤8：若计算机程序模拟运行的时间T＜T₀，更新当前状态M即M＝M^*，回到2重新执行；否则令s_uoucfs＝stepsize，输出s_uoucfs；

所述的步骤二包括如下步骤：

步骤1：输入PN的初始状态M₀以及初始步长stepsize，不可观变迁集合T_UO，不可控变迁集合T_UC，步骤一的T₀及步骤一的输出s_uoucfs；

步骤2：初始化：令M＝M₀，

S₁＝s_uoucfs；

步骤3：若s_uoucfs≤2则S_uop＝s_uoucfs则输出S_uop，结束；

步骤4：若s_uoucfs＞2则重新计算预测步长，输出S_uop或者回到步骤3；

步骤5，根据

的值是否为0，分两种情况讨论如下：

5.1若

则参考步骤一，从初始状态M₀，以步长

预测；

5.2若

则从初始状态M₀，以步长

预测；

其中5.1步骤中：根据系统是否进入死锁，包括如下步骤：

5.1.1如果在T₀时间内一旦系统走到了死锁状态则令

5.1.2如果在T₀时间内，系统没有走入死锁状态，则令

5.1.3输出S_uop，结束；

同样的，5.2步骤中，根据系统是否进入死锁，包括如下步骤：

5.2.1如果在T₀时间内一旦系统走到了死锁状态则令

更新S₀，回到步骤3，重新执行；

5.2.2在T₀时间内系统没有走入死锁状态，则令

更新S₁，回到步骤3，重新执行；

所述的步骤三包括：

步骤1：输入PN的初始状态M₀，不可观变迁集合T_UO，不可控变迁集合T_UC及步骤二的输出S_uop；

步骤2：初始化，令M＝M₀，stepsize＝S_uop；

步骤3：从当前状态M，以步长stepsize预测，得到M下可以使能的变迁集合T_en及预测到的可达状态集合Q；

步骤4：将Q中不可观变迁相连的连续的状态划分为一类，称这类状态集合为Q_uo；

步骤5：若在M下

则根据步骤4得到含有状态M的Q_uo，更新当前状态M，即令M＝Q_uo，回到步骤3重新向下执行；

步骤6：若

选择发射t，到达新的状态M^*；

步骤7：若

对M进行分类讨论，确定发射的t，到达新的状态M^*；

步骤8：更新当前状态M即M＝M^*，回到3重新执行；

采用该方法对生产单元由6台分别为M₁，M₂，M₃，M₄，M₅，M₆的机器进行工件的加工，其中机器M₁，M₂的功能一样，M₃，M₄的功能一样，M₅，M₆的功能一样；具体步骤如下：

(1)首先确定所有资源：所述资源包括：16个装载工件的托盘、两个进程，每个进程各8个、机器M₁，M₂，M₃，M₄，M₅，M₆；

(2)确定与各资源有关所有操作及其先后顺序并建立其子模型：

(a)装载工件的托盘经历以下状态与活动：

进程1：

装载到机器M₁，M₂；

其上的工件被M₁，M₂加工；

装载到机器M₃，M₄；

其上的工件被M₃，M₄加工；

装载到机器M₅，M₆；

其上的工件被M₅，M₆加工；

加工完毕工件从M₅，M₆进行卸载；

用p1代表载有工件的托盘可使用，若其中含有托肯，表示可用的；p2，p3，p4分别表示托盘上的工件在被机器p9(M₁，M₂)，机器p10(M₃，M₄)，机器p11(M₅，M₆)加工之中；t₁，t₂，t₃分别表示机器(M₁，M₂)，(M₃，M₄)，(M₅，M₆)中装载工件，令t₁为不可观变迁，t₄表示从机器(M₅，M₆)中卸载工件；

(b)机器M₁，M₂，M₃，M₄，M₅，M₆经历以下活动和状态：

进程2的模型简化和上面进程1类似，有一点不同的是进程2的t₅是不可控的，也就是说进程2工件是否能装载到机器M₅，M₆上是不可控制的，有可能装载上，有可能不能装载上。

2.根据权利要求1所述的一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：所述的步骤一中步骤6，包括：

6.1，若T_en为空：令stepsize＝stepsize*2，更新步长stepsize，回到2重新执行；

6.2若T_en不为

考虑死锁状态M_dead和Q的关系，发射变迁到达新状态；

其中6.2步骤中，包括：

6.2.1

若

且t∈T_en，则随机发射变迁t∈T_en，到达新的状态M^*；

若

且t∈T_en，则随机发射变迁t∈T_uc，到达新的状态M^*；

6.2.2若

根据

是否为空，决定更新步长回到步骤2执行还是发射变迁到达新的状态；

上述6.2.2步骤中，包括：

6.2.2.1若

则stepsize＝stepsize*2，更新步长stepsize，回到步骤3重新执行；

6.2.2.2若临界状态集合

包括步骤：

1)若当前状态M是好状态即M∈M_good；

2)若当前状态M是临界状态即M∈M_CR；

其中，1)若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

若

且t∈T_en，则随机发射t∈T_uc，到达新的状M^*；

2)若当前状态M∈M_CR：

若

且t∈T_en，则从T_en中将发射到达坏死或者死锁状态的变迁剔除掉的集合中随机选择一个变迁t进行发射，到达新的状态M^*；

若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

3.根据权利要求1所述的一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：所述的步骤一中步骤7，包括步骤：

7.1若Q_uo中有至少一个状态没有可以使能的变迁，则令stepsize＝stepsize*2，更新步长stepsize，回到步骤3重新执行；

7.2若Q_uo中每一个状态都有可以使能的变迁，从上述步骤6的6.2开始向下执行。

4.根据权利要求1所述的一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：所述的步骤三中步骤6，包括：选择发射t和如下步骤：

6.1若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

6.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

5.根据权利要求1所述的一种含有不可观与不可控事件的自动制造系统无死锁控制方法，其特征是：所述的步骤三中步骤7，依据

分两种步骤：

7.1若M∈M_good，选择发射t；

7.2若M∈M_CR，选择发射t；

其中7.1步骤中，根据t变迁发射进行：

7.1.1若

且t∈T_en，则随机发射t∈T_en，到达新的状态M^*；

7.1.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*；

其中7.2步骤中，根据t变迁发射进行：

7.2.1若

且t∈T_en，则从T_en中将发射到达坏死或者死锁状态，或者是到达含有坏死或者死锁状态的Q_uo的变迁剔除掉的集合中随机选择一个变迁t进行发射，到达新的状态M^*；

7.2.2若

且t∈T_en，则随机发射t∈T_uc，到达新的状态M^*。

Images