一种求解最少时间最小费用路问题的算法

针对同时带有弧费用和弧时间的运输网络中最少时间最小费用路的问题,本文提出了一种算法。该算法能高效地求出此类网络中从源节点到目的节点的双目标最短路（最少时间最小费用路）。实例计算表明,该算法是有效的。     

求解最小费用最大流的新方法

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性     

最短路问题的改进算法

通过引入两个数组,从提高算法效率和增强寻路直观性两个方面对无回路网络最短路问题的权矩阵法进行了改进.改进后的算法既能快速的计算从源节点到其目的节点的最短路权又能更直观的找出最短路.最后算法分析和仿真结果表明,改进算法较权矩阵法相比,运算速度有了明显的提高,是计算无回路网络最短路的一种有效算法.     

最大动态流关键弧的改进算法

针对时间容量网络的最大动态流的关键弧问题,首先分析了经典的Ford-Fulkerson最大动态流算法,在此基础上简化了最大动态流算法,并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法。算法将计算新网络最大动态流时共有的最小费用路保留,去掉了自然算法中重复的计算。的效率更高。     

点和边有容量约束的网络最小费用最大流算法*

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明：点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。     

无线Mesh网络中基于最小权有限支配集的网关部署算法研究

无线Mesh网络中网关是网络性能的瓶颈,网关部署至关重要。本文对无线Mesh网络中网关QoS性能进行分析,提出基于最小权有限支配集,以部署费用为贪心策略的贪婪算法(Greedy_LDSC),该算法用贪心法提高了网关的性价比。同时,提出了基于最小权有限支配集改进的贪婪算法(Greedy_LDSI),以降低网关的部署费用。仿真实验表明,从网关性价比方面来看,Greedy_LDSC算法的网关性价比之和比基于最小权有限支配集的网关部署算法(GREEDY_LDS)要高;从网关部署费用方面来看,Greedy_LDSI算法的网关部署费用比GREEDY_LDS算法会低。     

基于最小生成树的LEACH路由算法研究

设计能量有效的路由协议以延长网络生存周期,提供优化可靠的网络服务成为资源有限的无线传感器网络研究的核心问题.为了节省无线传感器网络整体能耗,基于最小生成树理论,提出建立数据汇聚的最小能耗树.通过仿真比较.新的路由算法较优于传统LEACH路由算法.该路由算法能够延长网络生存周期,有效节省网络总能耗.     

基于动态规划的无线传感器网络的路由算法

路由问题是无线传感器网络中的核心问题之一,其数据传送的多跳特点使得非常适合用动态规划的原理来设计传感器网络的路由算法.基于动态规划,通过节点跳数生成算法为传感器网络中的每个节点赋一个表示到Sink点跳数的节点跳数值,并分析了传感器网络的拓扑结构特点,然后给出了无线传感器网络中寻找从源到汇满足不同设计目标的最小跳数(MinH)、最小跳数最大剩余能量(MinHMaxRE)和最小跳数最小费用(MinHMinC)3种路由算法.探讨了最小跳数最小费用路由与最小费用路由之间的关系,并给出了判断最小跳数最小费用路径就是最小费用路径的一个充要条件.算法的能量消耗分析表明,所给路由算法能实现大幅度的能量节省.     

MPLS网络中QoS路由算法研究

论文着重研究了MPLS网络中QoS路由算法的设计问题。MPLS协议本身提供了QoS路由的机制,但有效的QoS路由算法却是其实现的保证。论文首先推导出代价函数公式,然后在此基础上提出了最小代价路由算法(LCR),根据MPLS网络节点获得的信息计算满足特定的QoS需求条件的最小代价路径。在模拟环境中,通过与SPF算法对比,此算法在保持路径利用率和平衡网络负载等方面具有明显优势。     

最短路问题的位势法

给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法.这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶点势进行比较,按照势的由小到大顺序逐步得到其他顶点的势和路由,每次迭代要更新标准势;直到找到终点的势和路由为止.两种算法采用不同的标准势计算法.一种采用原标准势累加1的更新法,该算法仅适用于正整数费用网络;另一种利用弧割的概念寻找最小标准势来代替原标准势,该算法适用于正费用情形.证明了算法的正确性以及为说明算法的有效性给出了一个算例.最后通过与Dijkstra算法的比较分析了位势法的五条特点,得出结论:位势法是求解最短路问题的有效算法.     

基于混合粒子群算法的网格任务调度

减少分布式程序的执行时间是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。在研究网格环境下的任务调度的基础上,提出了一种用于解决DAG任务调度问题的通用混合粒子群优化算法(Common Hybrid Particle Swarm Optimization),简称为CHPSO。该算法将问题的解(粒子)表示为任务的调度优先权向量,采用混合粒子群优化算法探索解空间。实验结果表明,在求解不含孤立点的单个DAG调度问题时,该算法所得解的调度长度仅为HEFT的90%～92%,求解质量与PSGA相当;在多张DAG图(含孤立节点)并发执行的网格环境中,该算法的调度性能明显优于PSGA及文中列出的其它演化计算方法。     

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

基于拓扑序列归约的Web服务组合QoS度量算法

考虑有向无环图 (DAG)描述的组合服务模型,提出了一种新的组合服务QoS度量方法--基于拓扑序列归约的Web服务QoS度量方法（QCMTSR）。其借鉴迭代归约度量方法中的基本结构及QoS计算公式,定义了DAG图中的两类基本结构,串归约结构和并归约结构,并给出了两种基本结构的QoS属性计算公式;通过逐步归约DAG图拓扑序列中的每个节点,直至最后一个节点的QoS属性值就是组合服务的各QoS属性的度量结果。从理论上证明了QCMTSR算法适用于所有DAG描述的组合服务,并实验证明QCMTSR算法对可靠性和可用性能够更准确的度量。     

基于遗传粒子群优化的嵌入式系统软硬件划分算法

针对单处理器嵌入式系统软硬件划分问题,采用带权有向无环图进行建模,并将之约简,进而转换为多约束条件的0/1背包问题求解.由于基本粒子群优化算法无法求解0/1背包问题,故将遗传算法中的交叉、变异思想引入粒子群优化算法,提出了求解离散组合优化问题的遗传粒子群优化(GPSO)算法,采用两点交叉算子和非均匀变异算子对粒子的位置和速度更新方法进行了重新定义.实验结果表明,采用文中算法能有效地解决软硬件划分问题,具有良好的全局搜索能力,其寻优能力和执行时间优于遗传算法和模拟退火算法.     

同构计算环境中一种新的静态任务调度算法

延伸了TTIG模型并提出新的算法．在模拟实验中，将此算法与MATE和其它同构环境中基于DAG的调度算法，在不同测试条件下进行了比较，结果显示该算法性能明显优于MATE，与基于DAG模型的调度算法比较而言，在性能方面各有千秋，但在算法时间复杂度方面具有显著的优势．     

DAG Scheduling in Heterogeneous Computing and Grid Environments Using Variable Neighborhood Search Algorithm

DAG scheduling is a process that plans and supervises the execution of interdependent tasks on heterogeneous computing resources. Efficient task scheduling is one of the important factors to improve the performance of heterogeneous computing systems. In this paper, an investigation on implementing Variable Neighborhood Search (VNS) algorithm for scheduling dependent jobs on heterogeneous computing and grid environments is carried out. Hybrid Two PHase VNS (HTPHVNS) DAG scheduling algorithm has been proposed. The performance of the VNS and HTPHVNS algorithm has been evaluated with Genetic Algorithm and Heterogeneous Earliest Finish Time algorithm. Simulation results show that VNS and HTPHVNS algorithm generally perform better than other meta-heuristics methods.     

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题．目前任务调度算法中刻画任务依赖关系最流行的模型是DAG,在以前的文献中,提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境)．延伸了TTIG模型,并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2)．GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能．在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势．     

Topological ordering algorithm for LDAG

Directed Acyclic Graph (DAG) is an important tool for workflow modeling and data provenance management. In these applications, DAG usually performs well. Yet for some workflow applications, except data or control dependencies between atomic tasks, there exists another requirement that each atomic task should be accomplished at an expected stage. Therefore, this paper proposes an improved DAG model – LDAG, in which each vertex has a level. Three cases of the level of vertices are discussed. For a reasonable one of these cases, this paper proposes a topological ordering algorithm and proves its correctness. In addition, it discusses the complexity of the algorithm and some other relevant problems.     

无回路网络中最短路问题的高效算法

无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。 关键词：