《[2017年整理]生产与服务系统建模与仿真(上海交通大学)》由会员分享，可在线阅读，更多相关《[2017年整理]生产与服务系统建模与仿真(上海交通大学)（164页珍藏版）》请在金锄头文库上搜索。
1、 工 业 工 程 与 管 理 系Industrial Engineering （2） T=t1, , tm是变迁的有限集合，m(0)为变迁的个数； PT= ， PT ； （3） I：PTN是输入函数，它定义了从P到T的有向弧的重复数 或权(Weight)的集合，这里N=0, 1, 为非负整数集； （4） O：TP N是输出函数，它定义了从T到P的有向弧的重复数 或权的集合。在表示PN结构的有向图中，库所用圆表示；变迁用长方形 或粗实线段表示；若从位置p到变迁t的输入函数取值为非负整 数w，记为I I( (p p, , t t)=)=w w，则用从p到t的一有向弧并旁注w表示；若 从变迁t到位置
2、p的输出函数取值非负整数w，记为O O( (p p, , t t)=)= w w， 则用从t到p的一有向弧并旁注w表示。特别地，若w=1，则不必 标注；若I(p, t)=0 或O(p, t)=0，则不必画弧。I与O均表示为nm 非负整数矩阵，O与I之差C=O-I 称为关联矩阵。工 业 工 程 与 管 理 系Industrial Engineering I(p2, t1) = 1; I(p3, t1) = 0;I(p1, t2) = 0; I(p2, t2) = 0; I(p3, t2) = 1;p2p3p1t1t2O(p1, t1) = 0; O(p2, t1) = 0; O(p3, t1)
3、= 1;O(p1, t2) = 0; O(p2, t2) = 1; O(p3, t2) = 0.输入函数：输出函数：关联矩阵：工 业 工 程 与 管 理 系Industrial Engineering 有界性(Boundness);安全性(Safeness);守衡性(Conservativeness);活性(Liveness);可逆性(Reversibility)。工 业 工 程 与 管 理 系Industrial Engineering 给定一标识mt，是否可以激发一系列变迁从初试标识m0到 达该标识。定义定义: 若从m0始标识开始激发一个变迁序列产生标识mr，则 称mr是从m0可达的。若只
4、要从m0开始激发一个变迁即可产生mr ，则称mr是从m0立即可达的(Immediately reachable)。所有从m0 可达的标识的集合称为可达标识集或可达集，记为R(m0)。一般地，从m0到mr所激发的变迁序列表示为: srtj1, , tjr, 这里j1, , jr为1到m之间的整数。从m0激发sr产生mr表示为 ：m0srmr。工 业 工 程 与 管 理 系Industrial Engineering =0;(2) 而T-不变量为 (m1)非负向量y，并满足：CyCy=0=0(3) 将(1)式两边左乘xT，得到xTmk+1=xTmk+xTCvk。由(2)，则有x xT Tmmk k
5、+1+1= =x xT Tmmk k, , k k 0 0 (4) 特别地，从k=0开始递推有：xTm0=xTm1=xTm2=xTm3=xTm=常数，即x xT Tmm= =x xT Tmm0 0= =常数常数(5) 上式表明由由P-P-不变量加权的所有库所中初始标识数之和为常量不变量加权的所有库所中初始标识数之和为常量。或者说 ，P-不变量的非0元素是相应的库所中标识数的权值，使得在任何从m0可 达的m下所有库所中的标识加权和为常数。称这些库所被该这些库所被该P-P-不变量覆不变量覆 盖盖。基于PN制造系统性能分析工 业 工 程 与 管 理 系Industrial Engineering R
6、2=(d2+d4)i2;Rt=(d5+d6)(i1+i2)+d3i1+d4i2 例：赋时库所Petri网工 业 工 程 与 管 理 系Industrial Engineering 加工给定的混合工件所需的资源使用方案; 生产计划与调度的主要方法归纳如下： 数学规划法数学规划法: : 这种方法对于某些系统能够产生最优解,然而很少有真正地实际 应用的案例。数学模型必须忽略许多实际约束条件。原因是这 些约束条件，诸如材料搬运能力、复杂的资源的共享和复杂的 路径等是很难从数学上精确描述的。即便可以，复杂的代数方 程以及不等式也是非常难以理解。再者，在实际使用中，系统 的参数或结构略有变化，最优性就不成
7、立。 启发式派遣规则法启发式派遣规则法这是实际中广泛采用的方法。好的规则来源于人的经验，并的 确是有效的，但往往不是最优的。规则还可以通过系统仿真模 型来产生，但困难的是建立复杂的模型及需要进行繁琐的计算 。而且仿真方法往往是针对特定的问题，因此其结果的通用性 差.如：FCFS;EDD(Earliest Due Date);SPT(Shortest Processing Time)等规则。 人工智能法人工智能法该方法包括专家或基于知识的系统、基因算法以及神经网络方 法。基于知识的系统方法难以获取有效的规则与知识，因此不 能保证结果是最优的。基因算法与神经网络方法都需要相当大 的计算量，且难以形
8、成问题的模型。 其它方法其它方法其它方法包括代数模型法、控制理论法、CPM/PERT法以及排 队网络模型法等。代数模型法与控制理论法难以找到有效的求 解方法；虽然基于CPM/PERT法以及排队网络模型法具有效的 求解方法，但它们不能很容易地描述系统的资源共享、同步、 以及批次等调整。 赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering pi,j,k是一操作库所，它代表操作Oi,j,k的进行。 操作库所中的标识表示操作在进行之中。 pni,j,k是工件Ji的第j道工序后的第k个中间库所 ，它表示一个缓冲区。中间库所中的1个标识 表示
9、1工件正在等待下一道工序加工。 pmi是资源库所，表示机器i。pmi中的1个标识 表示1台机器可利用。 pfj,k代表工件Jj的第k个结束库所，它代表得到 Jj类工件的1个成品。 pij,k代表工件Jj的第k个起始库所，它表示加工 Jj的第k种原材料或半成品备好 .若Jj具有2个及 2个以上起始库所，则显然第一个工序为装配 工序 。工件工件J J1 1的模型的模型若工件J1在完成第一道工序加工后，需要与另 一零件装配在一起，则可用图4.10所示的PN 模型表示。图中pi1,2表示另一零件。 一般地，一工件只有1个结束库所，即k只取1。但 是在特殊情况下，可能具有1个以上结束库所。例 如，工件J
10、5与工件J1一直到由p1,2,3所表示的操作前 共享相同的工序序列，但它不再需要进一步加工 ，我们可以用图4.11所示的PN模型来表示。图中 pf5,1为这一工序序列的一个额外结束库所，表示得 到1个J5类型的成品。这一情况在化工过程中常常 见到，表示得到1种副产品。 赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering & Management工 件 J2 的 P N 模 型赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering & Management将J1与J2的模型
11、通过资源库 所关联在一起从而得到如 图所示的整个系统的模型 。必须注意在图中，出现 了2个pm2，这在PN中是不 允许的。实际上它们是同 一个库所，只是由于图形 布局的困难，只好将它们 分开。图中pm3的情况也是 如此。 赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering & Management在上述模型中，表示操作的库所都与一时延关联，它们分别对 于库所所表示的工序的时间。而资源库所与中间库所均为及时 库所，即它们的时延为0。因此：d(p1,1,1)=3；d(p1,1,)=4；d(p1,2,2)=3；d(p1,2,3)=2；d
12、(p2,1,1)=4；d(p2,1,3)=2；d(p2,2,1)=3；d(p2,2,2)=4；d(p2,2,3)=4；d(p1,1,1)=3；d(其它库所)0。系统的初始标识：m0(pi1,1)=1；m0(pi,1)=1；m0(pm1)=1； m0(pm2)=1；m0(pm3)=1；m0(其它库所)=0。 系统的目标状态为J1与J2加工结束，它由系统的目标标识表示， 即：mf(pf1,1)=1；mf(pf,1)=1；mf(pm1)=1；mf(pm2)=1；mf(pm3)=1 ；mf(其它库所)=0。 赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial E
13、ngineering & Management然而，即便是一简单的PN模型，其可达图也可能大得难以 全部产生。因此，我们不准备去产生整个可达图去枚举出所有 的路径，而是采用启发式搜索的方法，根据一定的启发规则产 生必要的局部可达图，并在这一局部可达图所代表的路径中选 择最好的路径。这一局部最优的调度计划对于整体来说可能不 是最优的，但确是好到可以接受(次优的)，而且能极大地缩短计 算时间。由此可见，这是一种在优化程度与计算时间之间的折 中方法。启发式搜索方法启发式搜索方法我们知道一旦建立了系统的PN模型，系统的状态变化可以用其 PN模型的标识变化来描述。因此，系统的性能完全可以通过其 可达图来
14、追踪。理论上讲，我们可以产生系统PN模型的可达图 ，从而找到从初始标识到目标标识的最优路径(调度计划)，即一 个变迁激发序列。这里，我们采用基于著名名的图形搜索法A*8的L1调度法。给定 某一PN模型，L1法从初始标识开始延伸可达图直到其所产生的 局部图触及目标标识。一旦达到目标标识，通过反向追踪标识的 父标识（若在m1下激发某变迁产生m2，则m1为m2的父标识）指 针的轨迹，构建优化路径。因此，该路径上的变迁激发序列给出 所有活动的开始的先后顺序，亦即调度计划。 赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering & Manag
15、ementL L1 1调度算法：调度算法： 第一步：将初试标识m0放在OPEN列表上。 第二步：若OPEN是空的，则停止，从而计算失败。 第三步：从OPEN中移去第一个标识m且放入CLOSED列表上。 第四步：若m是目标标识，则构建从初始标识到目标标识的优化路径，并结束。否则，执行第五步。 第五步：找出标识m下可激发的变迁。 第六步：对于每一可激发的变迁，产生其后续标识，并设置所有从后续标识到m的指针。计算后续标识m的g(m)。 第七步：对于m的每一后继m，进行以下步骤： (a) 若m已经在OPEN中，将其指针指向产生最小g(m)的路径。（说明1 ） (b) 若m已经在CLOSED中，将其指针
16、指向产生最小g(m)的路径。若m需要重新定向，则将其移入OPEN中。（说明2）(c) 计算h(m)与f(m)，且将m放入OPEN中。（说明3） 第八步：根据f(m)的递增顺序重新排列OPEN中的标识的顺序。第九步：跳转至第二步。 (说明4）赋时Petri网在FMS生产调度中的应用工 业 工 程 与 管 理 系Industrial Engineering & Management例：例：L L1 1调度算法的应用调度算法的应用 用L1算法求上例的最优或次优调度计划。 下面我们用下列不同的h函数应用L1算法求解： （1）h1(m)=0，对于所有标识；h1(m)使得f(m)等于g(m)，这意味着没有 采用启发信息。它选择下一标识使得从初始标识到该表示的实际成本最 小。这种归一的最好优先(uniformed best-first)搜索法对应着归一成 本法（uniform-cost）
