基于混合搜索的含逻辑“与”“或”的RM优化算法

相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.     

改进的单调速率调度算法

实时系统中调度算法起着重要的作用.单调速率调度算法(rate monotonic algorithm,RM)是一种被 广泛使用的调度算法,并且已被证明是一种最佳的静态优先级算法.传统的RM算法忽略上下文切换需要消耗的时间,针对此问题,提出了一种延迟抢占的改进方法.该方法考虑了上下文切换消耗时间对调度算法的影响,可以减少...     

多处理器单调速率任务分配算法性能评价

多处理器任务分配调度算法是一类经典实时调度算法，然而目前研究在如何根据任务集特征选择任务分配算法方面少见指导性原则，不利于提高多处理器任务分配算法的可调度率及使用尽可能少的处理器达到最优调度结果。基于两种多处理器任务调度策略的比较，本文给出划分策略下的多处理器RM调度的可调度条件和任务分配算法夏分析。仿真结果表明，各任务分配算法所需处理器数与任务集总利用率成正比。同时，分析总结出各算法适用范围及如何根据任务集利用率选择合适算法的指导原则。最后结果还表明，实际算法性能与理论性能界存在差异。     

基于命题投影时序逻辑的单调速率调度算法模型检测

提出了基于命题投影时序逻辑(propositional projection temporal logic,简称PPTL)的单调速率调度(rate monotonic scheduling,简称RMS)模型检测方法.该方法使用SPIN模型检测器的系统建模语言PROMELA为任务调度系统建模,使用PPTL描述系统期望的性质,通过SPIN验证系统模型是否满足性质,从而得知一个任务组在RMS下是否可调度.同时,RMS算法控制下的任务调度系统的其他性质也可以得到验证.     

单调速率任务分配算法利用率的界限分析

通过对单调速率任务分配算法调度策略和可调度条件的分析,在多处理器周期任务抢占调度模型基础上,细致刻画了任务分配算法如何分配任务的行为。依据Liu和Layland定理,给出多处理器下任务分配算法的最小RM利用率界的定理。仿真结果表明,分配算法的利用率界是不同特征任务集选择不同分配算法进行任务划分的关键,通过对任务集总利用率与算法利用率界的比较,判断使用该算法对任务集是否可以产生可行分配。     

基于单调速率的可调度性判定改进算法

在单调速率调度策略的基础上,提出一种改进的任务集可调度性判定算法。该算法通过设定时钟变量模拟调度过程中的系统时钟,在时钟变量值增长过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限的满足情况,判定任务的可调度性,从而确定任务集的可调度性。通过实例分析及与现有判定方法的比较,验证了该算法的正确性和高效性。     

基于线性规划的RTL可满足性求解和性质检验

采用线性规划作为基本工具开发一个RTL可满足性求解器,并将其应用于解决RTL性质检验问题．深入研究了使用线性规划约束对RTL电路元器件的建模方法,得到了一种对RTL电路建模的通用方法．通过将RTL性质转化为虚拟RTL电路,找到了一种验证RTL性质的方法．通过实验,并与采用zchaff布尔可满足性求解器的模型检验工具NuSMV进行比较,证明了基于RTL可满足性求解器的性质验证方法在内存和时间消耗上具有相当大的优势．     

混合实时事务的延期单调速率调度算法及其可调度性分析

对于含有实时和非实时两部分的混合实时应用,传统的单调速率调度算法(RM)已不再适用.为此,该文引入“混合实时事务”的概念,并针对这类事务提出一种延期单调速率调度算法(DRM);着重分析了DRM算法对混合实时事务的可调度性;进行了实验测试与性能分析比较．结果表明,事务集中混合实时事务占的比例越高,混合事务中非实时子事务占的比例越大,该算法的CPU使用率阈值就越高,且在各种情况下,DRM算法与RM算法相比性能都更优,最低情况也与之一样．     

基于线性规划的配方优化模型研究

为了解决养殖业饲料配方的优化问题,即在保证饲养原料的用量要求和营养元素的摄入量要求的前提下,使得饲养成本最低。提出了一套完整的转化规则,能够将配方优化问题转化为线性规划数学模型的标准形式,并且在转化过程中能够同时得到初始的基变量和基可行解。最后给出了基于“两阶段法”的优化算法,能够求出每一种饲养原料的正确用量。基于该算法的饲料配方软件已开发成功,通过在南京某乳品公司的实施,证明了该算法的可靠性和实用性。     

单调速率及其扩展算法的可调度性判定

任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体为下述3大类问题：（1）理想的RM算法下的可调度性判定的CPU利用率最小上界最小及可调度的充分必要条件;（2）考虑调度时间开销情况下的可调度性判定条件;（3）优先级反转协议及其对可调度性的影响.给除了具体实例来叙述上述问题,并从算法复杂度和可检测率两方面比较各种算法的优劣。     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

基于线性规划模型的高校排课系统

排课系统本质是一个多资源约束分配问题。本文对排课资源的约束条件和自身需求进行分析,建立了系统的线性规划模型,该模型具有直观性、易理解、可操作强等特点;在此基础上,采用蚁群算法进行仿真计算,实现资源分配的优化处理。系统用C#语言进行实现,效果良好。     

最优二叉搜索树的动态规划算法研究

动态规划算法的有效性依赖于问题本身具有最优子结构性质和子问题重叠性质。该文给出了用动态规划算法构造最优二叉搜索树的详细步骤,并用C 语言具体实现了该算法。用一定的空间换取时间,提高了解决本问题的效率。     

动态规划法构建最优二叉查找树的研究

提出动态规划法构建最优二叉查找树的算法模型,并对其进行改进,构造实例表明算法的有效性。     

基于线性规划的智能炼铁配料系统

以钢铁企业炼铁生产参数为研究资料,实现高炉炼铁配料优化、炼铁数据和三维模型的多元化展示.本文主要研究在Qt平台下设计研发了跨平台的智能炼铁配料系统,采用线性规划的方法建立炼铁配料的数学模型,利用单纯形法求解达到成本最优,以及利用FFmpeg库实现高炉数模动画的播放和OpenGL实现高炉三维模型的动态展示.本文首先介绍了系统利用到的一些相关技术,其次对系统的数据提取、更新、优化算法的设计进行了分析,最后对配料优化、数据的二维展示、三维模型的动态展示的实现和测试进行了介绍.     

基于BSP模型的大规模线性规划并行算法研究

在许多实际工程问题中经常遇到一些大型线形规划问题，通常的计算过程需要占用大量的计算时间，效率低下。文中提出了一种基于BSP模型的大规模线性规划并行算法——修正单纯形并行算法，分析了其代价函数和加速比，在所研制的集群计算机上进行了实现和测试。结果表明：当问题规模比较大时，此并行算法能获得较好的加速比。     

基于动态规划的最优二叉搜索树算法的改进

基于动态规划的最优二叉搜索树构造算法,选择子问题的划分时,r值的循环范围过大,存在不足。本文对此改进,缩小了r值的范围,算法时间复杂度由O(n3)减小至O(n2),并对两个算法的优劣进行了比较。     

基于线性规划的网络负载均衡技术

介绍了常用的负载均衡技术,分析了其局限性,并提出了一种基于线性规划的网络负载均衡技术。