串联加工网络关键路径的计算与扰动分析

文献[5]在极大代数上线性系统描述的框架下,通过关键路径研究了DEDS参数扰动对系统的影响,关键路径的计算是其核心问题,本文讨论了串联加工网络的路径的性质,在偏序科上运用动态规划的最优原理研究了DEDS的关键路径的计算问题,并给出了详细的算法。在此基础上,给出了扰动分析的新方法。

维普资讯 doc.guandang.net

第 3

期

2 0 9月 0 2年

自然科学南开大学学 Aca S in ir m at r lur ie s ttsNa k ln 1 t ce t u N t a i m v r i ai a Na ura un Uni e s u l Un v ri n. e ss a .

V o1 35 N93 . - Se p.2 002

文章编号：4 5 7 4 ( 0 2 0— 0 5 0 0 6—9 2 2 0 )30 5—5

串联加工网络关键路径的计算与扰动分析 李勇建邵秀丽涂摹生 (开大学信息技术科学学院，津，0 0 1南天 307)

摘

要

文献[]极大代数上线性系统描述的框架下，过关键路径研究了 D S参数扰动对系统的影响 .键路 5在通 ED关径的计算是其核心问题 .文讨论了串联加工网络的关键路径的性质，偏序图上运用动态规划的最优原理研本在究了 DE S关键路径的计算问题，给出了详细的算法 .此基础上，出了扰动分析的新方法 . D并在给

关键词：散事件动态系统；扰动分析；关键路径；极大代数；优原理离最 中图分类号： 1 TP 3文献标识码： A

0引

言

生产自动化的发展促使人们对生产线进行更深入的研究 .以前多采用排队论和仿真方法研究生产线. 之后在 8 O年代初期，出现了扰动分析方法 (文献[]和极大代数上线性系统的方法 (文献[] .见 2)见 1 )文献 [,]用极大代数上线性系统的思想，立了串、行生产线的状态方程，分析了其稳态特性. 3 4运建并并文献[ 5对具有存储器的串行生产线，定义了关键路径，究了关键路径的特性，通过关键路径分析了参数扰动研并

对系统性能的影响.献[]串联加工网络引入了关键路径，文 6对并研究了扰动分析方法；文献[] 7利用关键 路径的概念证明了随机串行生产线稳态性能函数可微的充要条件是系统的关键路径以概率 1的唯一，揭示了 DE S稳态性能函数不可微的内在原因.键路径的提出简化了离散事件动态系统的扰动分析方 D关法，对系统的扰动分析研究转化为对关键路径上事件的扰动分析问题.此用关键路径的概

念来研究使因

D DS的参数优化设计问题不仅直观， E而且有效 .文在文献[,]本 5 6的基础上，偏序图上运用动态规划的在 最优原理对串联加工网络的关键路径的计算给出了算法，考虑了缓冲器有限时系统产生阻塞的影响.对这于计算参数扰动系统性能的影响是重要的.后，于关键路径计算算法，出了扰动分析的新方法.最基给

1系统描述 考虑如图 1所示的串联加工网络.系统由加工站， …, m+ 1中含 n台并列且功能相同的加工机器 .…, m, ),, 站，它们分别包含一台机器 (一记号，为统记器，容量为 b假定其 . 一

”,+串接而成， 每个加工站 ( 0 1 一，,其中。工件预处理站，+为终处理为

和

+ B(Ⅲ, 一 1 2…,+ 1,, m )为加工站之间的存储 .,,依次进入。…,+加工，件在任 .以…, 工

不饥饿， c川阻塞，件 不工

加工站中的一台机器上加工，所有可能发生的排队 (例如，冲器中的工件，缓同一工作站中等待工作的空

闲机器，等待解阻塞机器 )都遵循先到先排队的原则.

收稿日期： 0 0 0— 7 2 0—92基金项目：家攀登计划基金 ( 72 1 1 )国家自然科学基金 (9 7 0 3国 90107, 6 641)

作者简介：奎曼霉 17-)山度理论与应用及人力资源优化等领域研究生，要从事D D仿真与优化、I理论及其优化方法， 93 ..杰笪市： .., . 博士主 ES CMS词