正规Petri网及其逆向最优调度

Normal Petri Net and Its Backward Optimal Scheduling

中文关键词  Petri网  正规网  最优调度  对偶问题

英文关键词  Petri net  normal Petri net  optimal scheduling  dual problem

中文摘要

      常规Petri网的变迁发生规则是正向的，即根据输入库所的标识确定授权变迁集，再从中选择发生变迁集并修改输出库所的标识．这一方面造成了冲突，另一方面使得对于一个预期的目标标识，不能按照系统成本最低或利润最大的原则来确定变迁的发生．为此本文提出了正规Petri网的概念并研究了它的两种级联方式──并联正规网和串联正规网，以及逆正规网这一重要概念．对于上述的最优问题，我们提出了逆向的授权规则，即根据目标输出标识确定发生变迁集，再由发生变迁集确定输入标识．并且进一步把这类最优调度问题转化为整数规划问题．最后我们研究了上述最优调度的对偶问题并将它转化为逆正规网的原问题来加以求解．

英文摘要

      The transition firing rule of conventional Petri nets is forward，which means the enabled transitions are determined by the pre-set markings of places，then the firing transitions are chosen from which are enabled. This on the one hand results in conflict and contact，on the other hand makes it impossible to determine the transition firings according to the criteria of mininmal cost or maximal profit. To solve this problem the paper presents the new concept of normal Petri net，then investigates two kinds of its connections-parallel normal net and series normal net. Further more the notation of reverse normal net is introduced. Considering the optimal problem mentioned above，the backward enabling rule is presented,which determines the firing transitions according to the target markings, then the initial markings are determined by the firing transitions. In such a way the optimal problem is translated to the integer program problem. At last the dual problem of the above problem is studied and is converted to the originalproblem of reverse normal net.