基于蚁群算法的参数相关网格任务调度算法研究

任务调度是网格计算环境中影响系统性能的重要问题,目前大多数调度算法在调度时均把任务假定为元任务,而忽略任务间的约束关系。利用图论的思想将任务间依赖关系描述为满足一定条件的有向无环图（DAG）,通过DAG图可以精确描述任务的优先级,此外蚁群算法在元任务调度中能有效实现任务调度和负载均衡,因此在蚁群算法进行元任务调度结果的基础上,根据任务优先级对分配给资源的任务进行排序即得出了参数相关任务调度的结果。仿真结果显示,此方法在各种网格环境下均能解决相关任务的调度问题,而且保证系统的负载均衡。     

网格任务调度的有向超图划分算法

网格计算是当前一个活跃的研究领域,其中任务调度是一个重要部分.根据网格环境下任务调度及传统DAG图的特点,吸取有向超图的优点,将有向超图理论融合任务调度特征,建立了基于划分的网格任务调度有向超图模型,并在此基础上通过对网格有向超图的划分实现任务对网格资源的映射与调度,提出了一种基于有向超图划分的网格任务调度算法HPGTS.模拟仿真实验结果证明了该模型及其算法的有效性和优越性.     

考虑合成机制的多星应急任务调度

以应急任务优先调度为原则,保证观测总收益的基础上最小化对原调度序列的扰动是多星应急任务调度领域急需解决的问题。首先,分析应急任务完成时间和观测收益关系,建立考虑时间依赖性收益的数学规划模型。其次,基于遗传算法,提出考虑合成机制的多星应急任务调度算法。设计任务合成、插入和替换算子完成应急任务插入,考虑任务观测收益、序列扰动和最短观测时间设计适应度函数,设计交叉、变异、全局修复算子迭代优化调度序列。最后,通过数值实验表明设计的算法能够显著提高调度质量,适用于多星应急任务调度问题。     

资源约束下多项目调度的拓扑优化方法

为了有效解决带有项目优先权约束和资源约束的多项目调度问题,综合考虑项目调度过程中任务的时序关系和资源限制,以拓扑遍历方法为基础,提出了一种多项目调度问题的拓扑优化算法。该算法利用拓扑序列的特点,能够保证任务间的时序关系,采用关键路径任务优先、向后影响度大以及最小空闲时间等优先规则进行任务调度及资源分配。结合工程实例,验证了该算法的可行性。     

基于八叉树优化的MoM-PO/PTD混合算法分析目标电磁散射及辐射问题

在综合利用矩量法(method of moments, MoM)和物理光学(physical optics, PO)方法的过程中, 要精准识别和划分PO位置处于点光源照射情况下的暗区和亮区。传统的识别划分手段的时间复杂度为O(N²), 当面片数量N增多时, 所需的时间呈现出急剧增长的趋势。文中应用八叉树和后向追踪算法, 对PO亮区判断过程进行加速, 可将时间复杂度由N²降为NlgN。由于计算PO区域电流时没有考虑边缘绕射造成的影响, 导致计算误差较大。鉴于此, 本文在计算过程中引入物理绕射理论对混合算法加以改进, 并通过与FEKO中的MoM相比较, 说明了修正后的混合算法能够有效提升计算精度。     

资源约束条件下任务调度算法研究

如何解决资源约束条件下的任务调度问题，保证在资源使用存在冲突情况下, 多个任务高效执行, 其中合理的任务调度和资源冲突消解是影响任务执行效果的关键因素。基于工作流图模型提出了一套资源约束条件下任务调度的框架, 并针对调度过程中产生的资源冲突, 提出了两种任务调度算法: 一种算法通过任务关键度确定优先级, 并基于贪心策略和调整工作流图拓扑结构的方法, 在任务开始前确定任务调度方案; 另一种算法采取弹性资源调度的方式, 使产生冲突的任务优先在资源不足的条件下开始执行, 任务调度和执行交替进行。最后, 通过地震救援案例验证了相关算法可行性, 与求解资源约束条件下任务调度问题的两类典型方法中具有代表性的算法进行对比实验, 分析了所提两种算法的优势与意义。仿真结果表明，所提算法具有适用地震救援资源紧缺特点的优势。     

多UCAV协同控制中的任务调度问题研究

任务调度包括任务分配和任务排序两个紧密耦合的问题,是多UCAV协同控制的核心和有效保证。分析了任务和UCAV的特性,针对带时间约束的复杂情况,建立了多机协同任务调度的数学模型。通过建立可行解到粒子间的映射,设计了粒子群优化算法求解,仿真实验验证了算法的可用性和有效性。     

基于空间几何模型的遥感卫星任务分解算法

遥感卫星调度问题包含资源约束和任务约束,约束条件比较复杂,在调度前需要将观测任务分解为能被调度算法处理的元任务。任务分解的核心是计算卫星观测目标的时间窗口和侧摆角,由于区域目标无法被单次完全观测,在进行分解时需要将其划分为若干个子区域。针对点目标,提出了一种基于空间几何模型的任务分解算法,在此基础上结合动态划分方法,提出了区域目标任务分解算法,并分析了区域划分参数与观测效率的关系。实验结果验证了算法的有效性。     

基于扩展时间影响网络的作战任务效能计算方法

由于战场环境的复杂性,作战任务与作战目标间通常存在动态不确定的因果影响关系。目前,传统的解析模型及作战模拟方法在计算作战任务效能时,存在因果建模能力不足,运行效率低下的问题。通过引入时间影响网络,并利用循环弧和强度参数扩展其时间约束,进一步表达了作战行动间异步和同步关系,提出了一种基于扩展时间影响网络的作战任务效能计算方法。在一定作战想定背景下,结合登岛作战任务示例验证了该方法的可行性和有效性。     

面向异构分布式计算环境的并行任务调度优化方法

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是NP(non deterministic polynomial)完全问题。首先给出了异构分布式计算系统的形式化描述,建立了静态任务调度问题的理论体系,通过分析总结最长动态关键路径(longest dynamic critical path,LDCP)算法的核心思想及存在的不足,提出一种运用结点信息流量减少CPU空闲时间碎片的并行任务调度优化算法,其时间复杂度为O(M×N3)。实验表明改进后的算法在调度长度、加速比及计算效率3个指标上均优于LDCP算法和分层结点排序算法(sorted nodes in leveled directed acyclic graph division,SNLDD),其中,与LDCP、SNLDD相比,调度长度平均缩短19.03%、8.02%,加速比平均提升18.42%、7.96%,计算效率平均提高10.17%、3.72%,进一步提高了并行系统的资源利用率。     

Scheduling algorithm based on critical tasks in heterogeneous environments

Heterogeneous computing is one effective method of high performance computing with many advantages. Task scheduling is a critical issue in heterogeneous environments as well as in homogeneous environments. A number of task scheduling algorithms for homogeneous environments have been proposed, whereas, a few for heterogeneous environments can be found in the literature. A novel task scheduling algorithm for heterogeneous environments, called the heterogeneous critical task （HCT） scheduling algorithm is presented. By means of the directed acyclic graph and the gantt graph, the HCT algorithm defines the critical task and the idle time slot. After determining the critical tasks of a given task, the HCT algorithm tentatively duplicates the critical tasks onto the processor that has the given task in the idle time slot, to reduce the start time of the given task. To compare the performance of the HCT algorithm with several recently proposed algorithms, a large set of randomly generated applications and the Gaussian elimination application are randomly generated. The experimental result has shown that the HCT algorithm outperforms the other algorithm.     

面向连续系统并行仿真的任务调度算法

任务调度是并行分布计算中最具有挑战性的问题之一。如何合理、有效地地进行任务调度,将直接影响到系统的并行效率。本文通过对连续系统仿真程序特点的分析,折衷考虑了负载平衡与通讯延时两方面因素对并计算的不同影响,提出了一种以系统总的开锁最小为目标的启发式调度算法。该算法在我们研制的长缨三号（ＣＨＹ－Ⅲ）并行机上经验证,具有良好的并行效率。     

基于试探性的卫星数传任务调度算法研究

卫星数传任务调度问题是一个非常复杂的组合优化问题,即如何合理为每个任务分配地面站资源及其服务时间以最大限度满足任务需求的问题。根据卫星数传任务的特点,首先建立了卫星数传任务框架模型,进而提出了任务执行灵活度、执行冲突度等概念,在此基础上提出了一种基于试探性的卫星数传任务调度算法。最后利用AFIT基准数据进行仿真验证,结果表明该算法是可行的。     

一种灵巧同构系统的任务静态调度算法

针对高性能的灵巧同构系统计算环境特点,提出了一种多处理机的任务静态调度算法。该算法结合遗传算法和启发式列表调度算法,具有较短的调度时间;算法考察了多处理机调度中的任务间前趋关系、通信关系以及任务存储量要求,具有实用意义。仿真结果表明,与标准算法和CP/MISF(critical path/most immediate successors first)算法比较,所提出的算法能够得到较优的调度结果。     

异构计算系统任务调度的遗传算法及改进

提出一种新的染色体编码方法——逆排序消出结点法RSEEN,确保染色体对应的任务分配调度为合理调度,不必在遗传操作过程中不断地验证和调整基因以保证染色体的有效性,简化了遗传操作,使优良基因更易保全并传递给后代,种群的进化过程更接近自然的进化法则。另外,还采用了启发式变异方法,加速了算法的收敛性。同时,构造本算法是以异构计算系统模型为基础的,充分考虑了任务间数据交换的开销和处理机间的差异,算法的应用更有普遍意义。     

基于多目标遗传算法的卫星成像任务调度技术

针对成像卫星的任务调度问题,考虑多种约束条件,提出了成像任务约束图模型。基于多目标优化和遗传算法思想,提出了一种应用于卫星成像任务调度的多目标遗传算法,详细分析了算法的各个关键步骤的设计思想,能够求得基于成像约束图模型的满意解,生成卫星的优化拍摄计划。卫星成像任务调度原型系统的实现和实验结果验证了该模型和算法的合理性和有效性。     

An optimal scheduling algorithm based on task duplication

1.INTRODUCTION Anefficientschedulingofaparallelprogramontothe processorsisvitalforachievingahighperformance fromaparallelcomputersystem.Thetaskduplication basedschedulingisanewapproachtothescheduling problems.Sincethecommunicationtimeamongtasks assignedtothesameprocessorisconsideredtobe negligible,taskduplicationisonewayofreducingthe interprocessorcommunicationoverhead.Usingthis approach,someofthemorecriticaltasksofaparallel programareduplicatedonmorethanoneprocessor.Thiscanpotentiallyred…     

面向协同设计的任务调度问题研究

针对协同设计任务调度存在的问题,综合考虑了协作项目间、任务间及任务自身的具体因素和约束,在建立设计任务网络图的基础上,提出了一种以"任务优先系数"为指标的可并行执行任务集内任务的执行调度算法.综合考虑协同设计过程中的诸多动态、不确定性及非量化等因素,基于均衡一适度原则建立了任务到团队成员分配的扩展数学模型,并利用匈牙利算法进行求解.研究表明,该方法能有效对复杂产品的协同设计流程进行规划,且简单易用.