生产管理知识-生产系统建模与仿真概述(ppt 156页)

工 业 工 程 与 管 理 系 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到位置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; p2 p3p1 t1t2 O(p1, t1) = 0; O(p2, t1) = 0; O(p3, t1) = 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可达的。若只要从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 x T T mmk k+1 +1 = =x x T T mm k k , , k k 0 0 (4) 特别地，从k=0开始递推有： xTm0=xTm1=xTm2=xTm3=xTm=常数，即 x x T T mm= =x x T T mm 0 0 = =常数常数(5) 上式表明由由P-P-不变量加权的所有库所中初始标识数之和为常量不变量加权的所有库所中初始标识数之和为常量。或者说 ，P-不变量的非0元素是相应的库所中标识数的权值，使得在任何从m0可 达的m下所有库所中的标识加权和为常数。称这些库所被该这些库所被该P-P-不变量覆不变量覆 盖。盖。 基于PN制造系统性能分析 工 业 工 程 与 管 理 系 Industrial Engineering R2=(d2+d4)i2; Rt=(d5+d6)(i1+i2)+d3i1+d4i2 例：赋时库所Petri网 工 业 工 程 与 管 理 系 Industrial Engineering 加工给定的混合工件所需的资源使用方案; 生产计划与调度的主要方法归纳如下： 数学规划法数学规划法: : 这种方法对于某些系统能够产生最优解,然而很少有真正地实际 应用的案例。数学模型必须忽略许多实际约束条件。原因是这 些约束条件，诸如材料搬运能力、复杂的资源的共享和复杂的 路径等是很难从数学上精确描述的。即便可以，复杂的代数方 程以及不等式也是非常难以理解。再者，在实际使用中，系统 的参数或结构略有变化，最优性就不成立。 启发式派遣规则法启发式派遣规则法 这是实际中广泛采用的方法。好的规则来源于人的经验，并的 确是有效的，但往往不是最优的。规则还可以通过系统仿真模 型来产生，但困难的是建立复杂的模型及需要进行繁琐的计算 。而且仿真方法往往是针对特定的问题，因此其结果的通用性 差. 如：FCFS;EDD(Earliest Due Date);SPT(Shortest Processing Time)等规则。 人工智能法人工智能法 该方法包括专家或基于知识的系统、基因算法以及神经网络方 法。基于知识的系统方法难以获取有效的规则与知识，因此不 能保证结果是最优的。基因算法与神经网络方法都需要相当大 的计算量，且难以形成问题的模型。 其它方法其它方法 其它方法包括代数模型法、控制理论法、CPM/PERT法以及排 队网络模型法等。代数模型法与控制理论法难以找到有效的求 解方法；虽然基于CPM/PERT法以及排队网络模型法具有效的 求解方法，但它们不能很容易地描述系统的资源共享、同步、 以及批次等调整。 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering pi,j,k是一操作库所，它代表操作Oi,j,k的进行。 操作库所中的标识表示操作在进行之中。 pni,j,k是工件Ji的第j道工序后的第k个中间库所 ，它表示一个缓冲区。中间库所中的1个标识 表示1工件正在等待下一道工序加工。 pmi是资源库所，表示机器i。pmi中的1个标识 表示1台机器可利用。 pfj,k代表工件Jj的第k个结束库所，它代表得到 Jj类工件的1个成品。 pij,k代表工件Jj的第k个起始库所，它表示加工 Jj的第k种原材料或半成品备好 .若Jj具有2个及 2个以上起始库所，则显然第一个工序为装配 工序 。 工件工件J J 1 1 的模型的模型 若工件J1在完成第一道工序加工后，需要与另 一零件装配在一起，则可用图4.10所示的PN 模型表示。图中pi1,2表示另一零件。 一般地，一工件只有1个结束库所，即k只取1。但 是在特殊情况下，可能具有1个以上结束库所。例 如，工件J5与工件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的模型通过资源库 所关联在一起从而得到如 图所示的整个系统的模型 。必须注意在图中，出现 了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(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 Engineering & Management 然而，即便是一简单的PN模型，其可达图也可能大得难以 全部产生。因此，我们不准备去产生整个可达图去枚举出所有 的路径，而是采用启发式搜索的方法，根据一定的启发规则产 生必要的局部可达图，并在这一局部可达图所代表的路径中选 择最好的路径。这一局部最优的调度计划对于整体来说可能不 是最优的，但确是好到可以接受(次优的)，而且能极大地缩短计 算时间。由此可见，这是一种在优化程度与计算时间之间的折 中方法。 启发式搜索方法启发式搜索方法 我们知道一旦建立了系统的PN模型，系统的状态变化可以用其 PN模型的标识变化来描述。因此，系统的性能完全可以通过其 可达图来追踪。理论上讲，我们可以产生系统PN模型的可达图 ，从而找到从初始标识到目标标识的最优路径(调度计划)，即一 个变迁激发序列。 这里，我们采用基于著名名的图形搜索法A*8的L1调度法。给定 某一PN模型，L1法从初始标识开始延伸可达图直到其所产生的 局部图触及目标标识。一旦达到目标标识，通过反向追踪标识的 父标识（若在m1下激发某变迁产生m2，则m1为m2的父标识）指 针的轨迹，构建优化路径。因此，该路径上的变迁激发序列给出 所有活动的开始的先后顺序，亦即调度计划。 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management L 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中，将其指针指向产生最小g(m)的路径。 若m需要重新定向，则将其移入OPEN中。（说明2） (c) 计算h(m)与f(m)，且将m放入OPEN中。（说明3） 第八步：根据f(m)的递增顺序重新排列OPEN中的标识的顺序。 第九步：跳转至第二步。 (说明4） 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 例：例：L L 1 1 调度算法的应用调度算法的应用 用L1算法求上例的最优或次优调度计划。 下面我们用下列不同的h函数应用L1算法求解： （1）h1(m)=0，对于所有标识；h1(m)使得f(m)等于g(m)，这意味着没有 采用启发信息。它选择下一标识使得从初始标识到该表示的实际成本最 小。这种归一的最好优先(uniformed best-first)搜索法对应着归一成 本法（uniform-cost），且能确保得到最优解。 （2）h2(m)=-dep(m)，这里dep(m)是标识m在可达树中的深度，即从初试 标识到达m激发变迁的次数； h2(m)侧重那些在可达树中较深的标识，即 ：f(m)=g(m)-dep(m)。因此，即便某一标识具有大的成本，若该标识较 深，则其成本将被补偿。 （3）h3(m)=min(rt1m, rt2m, , rtkm)，这里rtim, i=1, 2, , k是在标识m下具 有一标识的库所的剩下的延迟时间。 h3(m)侧重延迟最早结束（操作最 早完成）的标识。完成某一操作将使得其占用的资源可用于其它操作。 （4）h4(m)=h2(m)+h3(m)，h4(m)综合h2(m)与h3(m)。 除了h1(m)以外，上述其它启发函数都企图在较短的时间里找到次优解。 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 表4.6 运算结果 h函数迭代次数最终标识 的深度 最优路径 的成本 变迁激发序列 h1(m)5086tb2,1,3 tb1,1,1 te2,1,3 te1,1,1 tb2,2,1 tb1,2,3 te1,2,3 te2,2,1 h2(m)1386tb2,1,3 tb1,1,1 te2,1,3 tb2,2,2 te1,1,1 tb1,2,3 te1,2,3 te2,2,2 h3(m)5486tb2,1,3 tb1,1,2 te2,1,3 tb2,2,1 te1,1,2 tb1,2,3 te2,2,1 te1,2,3 h4(m)5386tb2,1,3 tb1,1,1 te2,1,3 te1,1,1 tb2,2,1 tb1,2,3 te1,2,3 te2,2,1 迭代次数是计算机程 序重复主路径的次数 。 目标标识的深度表示 从初始标识到达目标 标识激发变迁的总次 数。 路径的成本为产生的 调度计划完成时间。 由于探察一个新产生 的标识需要一次迭代 ，因此迭代的次数总 是等于或大于目标标 识的深度。 表中的变迁激发序列 就是调度计划。 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 表4.7 使用h1(m)的调度计划 h1(m)操作顺 序 操作时 间 1O2,1,32 2O1,1,13 3O2,2,13 4O1,2,32 累计操 作时间 10 计划完 成时间 6 表4.8 使用h(m)的调度计划 h(m)操作顺 序 操作时 间 1O2,1,32 2O1,1,13 3O2,2,24 4O1,2,32 累计操 作时间 11 计划完 成时间 6 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 表4.9 使用h3(m)的调度计划 h1(m)操作顺序操作时间 1O2,1,32 2O1,1,24 3O2,2,13 4O1,2,32 累计操 作时间 11 计划完 成时间 6 表4.10 使用h4(m)的调度计划 h(m)操作顺序操作时间 1O2,1,32 2O1,1,13 3O2,2,13 4O1,2,32 累计操 作时间 10 计划完 成时间 6 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 在表4.6中，所有产生的计划都有相同的成本，或者完成时间6 。在表4.74.10中，各调度计划的操作时间串起来累计为10或 11。这表明所有调度计划都不同程度上实现了并行操作。 注意到h2(m)显著地减少了迭代次数，即比h1(m)的情况减少了 74%。这意味着程序采用h2(m)化短得多的时间产生了具有相同 的完成时间的同样优化的调度计划。表明了启发函数的作用。 而h3(m)略微增加了产生具有相同的完成时间的优化调度计划 所需的迭代次数。这表明仅侧重较早结束的操作，实际上在资 源共享交互作用的环境下的启发作用并不大。还要注意到，在 h4(m)的情况下，h3(m)的作用大于h2(m)的作用，而起主导作用 。 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 列表OPEN中保持着已产生但尚未探察的标识，它们构成了可达图的前 沿。可达图不断从初始标识通过推进其前沿而成长直至到目标标识。 因此，本算法不产生整个可达图，而是一层一层地产生可达图直至找 到指向目标标识的最优路径。 (Go back) 列表CLOSED中保持着所有产生且已经探察了的标识，即那些已经与 目标标识比较并发现不是目标标识的标识。 (Go back) L1使用标识m的函数f(m)=g(m)+h(m)。f(m)为成本估计，它是经过m的 从初始标识到目标标识的最优路径的成本。g(m)是从初始标识到当前 标识的当前最底成本。h(m)为从标识m到目标标识的最优路径的成本 的估计。 (Go back) 说明1：若m已经在OPEN中，则意味着又发现一从初始标识到m的新 的路径。新的路径的成本g(m)必须与老的成本进行比较，选择具有最 小成本的路径。由于m仍然在OPEN中，它可以进一步被探察 。 (Go back) 赋时Petri网在FMS生产调度中的应用 工 业 工 程 与 管 理 系 Industrial Engineering & Management 说明2：若m已经在列表CLLOSED中，则意味着m已经被探察且某一到 m的新的路经已经找到。由于m已经被探察，m的一些后继标识已经产 生。若一直追踪指向后续标识的路径下去，则发现每一路径均在OPEN中 的某一标识结束。若指向m的新的路径成本比老路径低的化，则有2种处 理方式供选择。 其一，指向m后继标识的路径可被重新定向，所引起的变化一直传播到 OPEN中的标识为止。