基于广义随机Petri网的网格调度模型

针对网格资源调度中负载不均衡问题,在基于QoS且具有容错性的任务调度算法基础上提出一种基于任务优先级的QoS约束参数的调度策略。采用广义随机Petri网建立网格调度模型,增加Petri网的抑制弧功能,实现优先调度策略。结果证明了该策略优先运行紧迫任务,并且其运行任务时间和费用的综合代价较小。     

带抑制弧的时延着色Petri网模型检测技术

带抑制弧的时延着色Petri网(Timed Colored Petri Nets with Inhibitor Arcs,TCPNIA)是一种描述实时嵌入式系统的模型。给出了从TCPNIA到时间自动机的结构化转换算法,以利用变迁冲突调解机制保证TCPNIA模型和转换后的时间自动机模型语义等价;并给出了语义等价的证明和算法复杂度分析。层次化方法被用来提高模型检测的时间与空间效率。通过实际案例展示了该技术的应用和可行性。     

基于树型Petri网的网格资源调度模型

讨论树型网格环境下独立任务的调度问题,把网格资源计算能力和网络通信速度的异构资源调度问题转化为线性规划问题。提出网格资源调度的树型Petri网模型,基于速度优先的启发式资源调度算法对树型Petri网模型进行性能分析,验证了树型Petri网的单口模式传输特点。     

基于Petri网的列控系统形式化分析方法

利用原型Petri网对列车控制系统建模难于实现,用带抑止弧的增广Petri网则可以较好地描述问题。将带抑止弧的增广Petri网作为计算模型,对列车控制系统的一些关键问题进行了建模并给出了两个控制子系统：车站调度子系统与区间运行子系统。车站调度子系统实现了对列车请求进入和驶离车站的协调控制,区间运行子系统则实现了闭塞区间的车辆的安全性控制、突发事件时(如遭遇雷击,信号丢失的情况发生等)的安全性处理和公路铁路交叉口的调度等。最后,利用S-不变量对模型的活性、可达性和有界性等给予了形式化的验证。     

基于CPN的进路式联锁调度建模及其分析

提出一种基于有色Petri网(CPN)的进路式联锁调度算法模型,其中包括对联锁调度过程中机车的任务内正常行驶、进路联锁运算、机车驶离任务路线、闯入未开放进路、故障处理恢复等情况建立了清晰的模型。并利用CPN Tools对模型进行仿真验证与分析,结果表明该联锁调度CPN模型正确模拟了井底机车运输调度,对于机车调度是安全可靠的。     

一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

网格计算资源调度的层次Petri网建模与分析

本文给出了网格计算资源的三层调度方案，并利用层次颜色Petri网对这一调度方案进行了建模与分析。对不同层次的资源调度建立了相应的颜色时延Petri网模型，不同层次的颜色时延Petri网模型可以有不同的行为表现，体现了网格计算资源的异构、自治等特点。给出了层次颜色Petri网的可迭任务图的概念及构造算法，并利用可达任务图，对网格计算资源调度系统的运行状态进行了分析。     

基于受控时间Petri网的车辆检测过程模型

针对汽车检测线运行效率评估及确保给定数量车辆检测时间最短的问题,通过分析检测过程中的驱动事件和状态演变,给出了车辆调度的约束条件,在此基础上把模型中的时间约束与受控Petri网相结合,提出了受控时间Petri网（Controlled Time Petri Nets）模型,采用该模型对检测线调度过程中的节拍控制与车辆调度进行可视化的建模与分析。实践表明对于多批次车辆检测任务采用该过程模型可明显缩短检测时间。     

基于三层混合编程模型的Petri网并行算法研究

为解决多核机群Petri网并行化过程中,运用MPI+OPenMP混合编程实现同步会出现死锁的问题,提出了基于三层混合编程模型的Petri网并行算法。首先,根据事务内存的同步优势,在多核机群环境下构建MPI+OPenMP+STM的三层编程模型;然后,对Petri网的几何模型与代数模型的并行化进行分析,建立MPI+OPenMP+STM三层结构的Petri网并行模型,并对三层混合编程模型的Petri网并行算法进行设计与分析;最后,通过示例进行编程验证,该算法的运行效率明显优于其他编程模式,而且Petri网的规模越大,其并行计算的效果就越明显。因此,该算法是多核机群环境下模拟Petri网并行运行的一种高效且可行的算法。     

基于带抑制弧的Petri网表示的嵌入式系统模型的子网化简

基于Petri网表示的嵌入式系统PRES+(Petri net based Representation for Embedded Systems)模型可以描述实时嵌入式系统。为了提高PRES+的建模能力,将抑制弧加入PRES+模型中,得到基于带抑制弧的Petri网表示的嵌入式系统PIRES+(Petri net with Inhibitor arcs based Representation for Embedded Systems)模型。PIRES+模型提高了建模和验证复杂嵌入式系统的能力,但是在建模和验证过程中存在状态空间爆炸问题。为了缓解这一问题,提出两种PIRES+模型的子网的化简规则,使得简化后的模型与原模型具有相同的可达性、实时性和功能性。     

基于Petri网的网格调度模型研究

网格环境具有异构性、动态性和不可靠性,为了合理而经济地利用资源,本文提出一个基于QoS且具有容错性的任务调度算法,以时间和费用的预算以及时间和费用的权重比值作为QoS参数。使计算过程和通信过程重叠,以隐藏网络时延。本文用随机Petri网模型描述网格环境中的任务调度模型;定义了随机Petfi肉的可达图,用来分析任务调度模型的性能。通过分析和模拟,反映此算法能够在满足用户的时间和费用的限制,具有容错性,任务完成时间短,以及综合花费少等优点。     

时间Petri网与GA-PSO算法相结合的并行测试

摘 要：并行测试任务调度方案在自动测试系统中一直是尚未解决的难题。本文基于Petri网理论的基础,建立了并行测试的时间Petri网模型,并且首次将GA-PSO算法引入到时间Petri网的变迁序列的寻找过程中,快速地求得了最优调度方案。仿真结果表明,本算法能够以较大的收敛概率快速地收敛,最终得到最优变迁序列。     

基于Petri网的JSP动态分类调度

以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,通过构建Petri 网控制器使系统的运行满足期望的目标,同时利用混合遗传算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等资源制约条件下的动态优化调度。为了保证生产的平稳性,最大限度地维持车间的生产能力,提出了针对不同的扰动进行分类处理的新方法,首先基于机床故障修复时间、工人离岗时间及取消订单包含任务的多少进行分类调度,然后根据机床故障修复后以及工人回岗后剩余任务的多少决定是否进行再一次的调度,最后对算法进行了仿真研究。     

基于优先级的任务调度与负载均衡模型研究

在分布式计算环境下，为了有效地利用计算资源、快速完成协同计算任务，提出了基于优先级的任务调度与负载均衡模型．首先根据就绪任务队列和任务调度器所处的位置以及两者之间的关系，将任务调度划分为集中式任务调度和非集中式任务调度两种方式，在此基础上，利用时间Petri网建模技术，分别给出了采用这两种任务调度方式的、基于优先级的任务调度与负载均衡模型，并对各种模型的特点进行了详细分析．以此模型为基础，可以利用现有的时间Petri分析技术，对采用上述任务调度方式的任务调度算法进行模拟和分析，以便找出满足给定条件的最优的任务调度算法．     

基于改进遗传算法的网格任务调度研究

网格任务调度是一个NP完全问题,它关注大规模的资源和任务调度,要求采用具有高效性的调度算法.提出了一种基于改进遗传算法的网格任务调度算法,在算法初始化种群产生时引入min-min算法和max-min算法,从而提高初始化种群的质量;算法迭代过程中采用了一种新的局部收敛判断以及改进的变异操作来防止局部收敛.仿真结果表明,该改进算法能更有效地解决网格任务调度问题.     

一种用于柔性制造系统仿真的图形Petri网软件工具

本文致力于图形Ｐｅｔｒｉ网软件工具—ＧＰＮＳＴ软件包的设计与实现。首先介绍了ＧＰＮＳＴ的结构和功能，分析了它在Ｐｅｔｒｉ网图形编辑和网结构分析方面的能力；其次正式定义了Ｐｅｔｒｉ网的扩展—赋时着色Ｐｅｔｒｉ网（ＴＣＰＮ），并且使用ＴＣＰＮ建立了柔性制造系统（ＦＭＳ）的简化仿真模型。利用这个模型，能基本实现ＦＭＳ的动态仿真，同时显示整个仿真的过程；最后将调度算法、启发式规则、ＴＣＰＮ模型和仿真结合起来，构成一个基于专家系统的调度器，产生出虽非最优，但是具有比较好结果的可行调度，有效地解决了动态仿真中的ＦＭＳ调度问题。     

面向优先级用户的移动边缘计算任务调度策略

随着移动终端处理的数据量及计算规模不断增加,为降低任务处理时延、满足任务的优先级调度需求,结合任务优先级及时延约束,提出了基于任务优先级的改进min-min调度算法（task priority-based min-min,TPMM）。该算法根据任务的处理价值及任务的数据量计算任务的优先级,结合任务截止时间、服务器调度次数制定资源匹配方案,解决了边缘网络中服务器为不同优先级的用户进行计算资源分配的问题。仿真实验结果表明,该算法可以均衡服务器利用率,并有效降低计算处理的时延,提高服务器在任务截止处理时间内完成任务计算的成功率,相比min-min调度算法,TPMM算法最多可降低78.45%的时延,提高80%的计算成功率;相比max-min调度算法,TPMM算法最多可降低80.15%的时延并提高59.7%的计算成功率;相比高优先级（high priority first,HPF）调度算法,TPMM算法最多降低59.49%的时延,提高57.7%的计算成功率。     

任务与资源双向匹配的动态任务调度策略研究

并行测试系统中的测试任务的执行时间是不确定的,测试任务过程具有随机性。为实现测试任务优化执行的目的,建立了并行自动测试系统的动态任务调动模型,并提出了基于测试任务剩余工作量和测试资源剩余负载的启发式调度规则,并在测试任务过程Petri网模型的运行演化算法中采用该规则,实现并行测试任务的动态调度。最后通过实例仿真,验证了该策略的可行性和优越性。     

基于OGSA的网格服务管理模型研究

网格服务管理是网格计算的核心问题。通过对于目前网格服务管理体系架构的三种模型进行分析和比较,基于开放式服务体系架构(OGSA),探讨了网格服务管理系统的功能需求,进而设计了一种层次化的网格服务管理模型HGSM,描述了模型的工作流程。将网格服务管理分为任务分解、静态调度和动态调度三种层次,讨论了HGSM的各个层次的相关功能模块,以有向无环图和高级随机Petri网分别对于任务分解和服务调度提出了相关算法,算法中的可实施谓词、随机开关、实施速率等描述可以直接在SPN求解软件的编程中实现,从而为构造一种层次化的网格服务管理模型提供一个可实现的有效途径。