基于分解优化的多星合成观测调度算法

某些卫星的侧摆性能较差, 必须进行合成观测以提高观测效率. 研究了多星联合对地观测中的任务合成观测调度问题. 提出了将原问题分解为任务分配与任务合成的分解优化思路. 任务分配为任务选择卫星资源及时间窗口; 任务合成则针对该分配方案,将分配到各卫星的任务按照轨道圈次分组, 分别进行最优合成. 采用蚁群优化算法(Ant colony optimization, ACO)求解任务分配问题, 通过自适应参数调整及信息素平滑策略, 实现全局搜索和快速收敛间的平衡.提出了基于动态规划的最优合成算法, 求解任务合成子问题,能够在多项式时间内求得最优合成方案. 依据分配方案的合成结果, 得到优化方案的特征信息, 反馈并引导蚁群优化算法对任务分配方案的搜索过程. 大规模测试算例验证了本文算法的效率.     

面向星地协同观测规划问题的改进人工蜂群算法

卫星和地面观测资源利用各自搭载的载荷可以完成灾害预报、环境监测、目标发现等任务,地面观测资源可以与卫星配合共同完成观测任务,提升任务观测效果.通过规划将众多的观测任务分配给有限的卫星、地面观测资源来执行可以让协同观测发挥作用,同时得出卫星和地面观测资源的协同任务执行方案,对任务规划提出了很高的要求.基于此,对星地协同观...     

基于对地观测需求分析的多星协同任务规划研究

由于对地观测的应用目标不同,各业务部门对遥感数据的需求存在差异。为了在多星协同任务规划中最大限度地满足用户提出的任务需求,构建了对地观测任务需求模型,整合了观测要素对于传感器的观测时限、空间分辨率和光谱需求,并基于改进层次分析法(AHP)评估了卫星资源对于任务需求的适宜度;进而,提出了以任务需求适宜度及任务优先级为优化子目标的约束满足模型,通过遗传禁忌混合算法实现了时空谱一体化的多星对地协同观测。以“一路”重点区域南海及周边地区为试验区域,结果表明,本文提出的方法取得的目标函数平均值及任务需求适宜度平均值较大,能够对成像点目标分配适宜观测的卫星资源。通过对比三种算法,本算法的运行时间较短,能够满足实际应用需求。     

多编组协同任务分配模型及DLS-QGA 算法求解

为解决多智能体编组协同任务分配问题, 定义任务、智能体编组和相关的分配过程变量, 建立以最高任务执行效率为目标的数学模型. 在问题模型中设计考虑资源损耗的编组资源能力更新机制, 提出用于求解该模型的动态列表规划和量子遗传算法的混合任务分配算法, 使用动态列表规划选择处理的任务, 利用量子遗传算法为选定任务分配最合适编组. 最后通过算例表明, 所提出的方法在解决时序逻辑任务分配时能够得到更优更稳定的方案.

     

基于网络优化算法的LAMOST焦面板观测模型

在大天区多目标光纤光谱天文望远镜LAMOST系统中,为了快速获得高效率的观测规划,根据天文统计数据和工程设计状况,利用网络优化的最大流算法,构造了固有观测范围内多轮任务分配的数学模型,基于VC实现和优化了该算法模型,并对观测完备率、光纤利用率、时间复杂性、计算资源需求等方面进行伞面分析.实验结果表明,算法模型,符合LAM-OST的基本观测要求,能够高速有效地实现一个焦面板上4000个观测单元对相应星象数目的观测分配.问题的解决,同时对未来解决大天区观测范围内复杂条件下的超大规模观测任务分配问题提供了重大参考.     

基于服务的异质作战实体协同优化研究

针对作战仿真中异质作战实体协同分配模型存在的信息交互及协同效能低的问题,建立了一种基于服务的作战实体协同分配模型.通过服务调用机制解决异质作战实体任务分配时的信息交互和共享,以基于能力向量的效用函数为适应度函数,应用遗传算法优化初始任务分配方案;以航空协同反潜为背景进行了仿真实例验证,仿真结果表明,优化后的任务分配模型在基本相近的时间内,能有效提高任务分配方案的效能,使得分配方案更逼近全局最优.     

基于顺序扩展一致性包算法的多无人机分布式任务分配

以异构多无人机协同执行复杂的耦合多任务为背景,提出一种求解分布式任务分配问题非死锁的顺序扩展一致性包算法.首先,建立考虑任务载荷资源、任务时序、威胁区等约束条件的时序多任务分配模型;其次,对一致性包算法的任务包构建过程和冲突消解规则进行扩展,并设计一种基于有向图深度优先搜索的方法进行任务方案的死锁检测和修正,以实现无冲突和无死锁的任务分配;然后,将关联任务之间的时序约束转化为软时间窗约束,利用顺序分层的策略进行求解;最后,为了提高任务分配结果的可靠性,采用Dubins曲线路径将航路规划耦合到任务分配中.仿真实验表明,所提出的算法能够快速有效地求解异构多无人机分布式耦合多任务分配问题,具备良好的最优性和时效性.     

基于任务分解与强化学习的多平台协同火力分配方法

为了有效求解多平台协同火力分配问题,根据“分而治之”的思想,基于任务分解策略将复杂的决策任务分解为子目标平台选择和子平台火力分配两个阶段,通过融合启发式算法和强化学习模型,提出一种新的强化学习求解方法(HARL),并以多平台联合火力打击为作战背景进行实验仿真.子目标平台选择层根据当前状态,基于强化学习策略选择攻击当前子目标最适合的火力平台;而子平台火力分配层则使用启发式算法为执行攻击任务的平台规划最优的火力分配方案.实验结果表明,融合启发式算法和强化学习的HARL方法相比于传统的强化学习算法武器消耗量减少15%以上,相比于经典的启发式算法求解时效性提升20%以上,表明该研究成果可为未来求解复杂作战决策问题提供有力的技术支持.     

基于扩展合同网的协同故障诊断任务分配研究

任务分配作为协同故障诊断技术的重要环节,任务分配机制的优劣直接影响到诊断效率和准确性。针对现有合同网协议存在分配效率低、任务量大时易造成单节点过于忙碌等问题,提出一种基于扩展合同网的协同故障诊断任务分配机制。首先利用Hash算法建立子故障任务与对应分配路径的分配知识库,为任务分配提供动态分配经验;其次将Dijkstra算法与合同网协议相结合,通过权衡故障诊断能力与路径权值来选择"性价比"高的任务分配节点。算法仿真表明,扩展合同网任务分配算法减少了通信量、提高了分配效率。     

基于长短期记忆神经网络的容器云队列在线任务动态分配

针对现有容器云在线任务分配方法分配合理性和资源均衡度较差、任务处理效率较低的问题,提出一种基于长短期记忆神经网络的容器云队列在线任务动态分配方法。描述容器云队列在线任务模型;以节点互补度、资源利用率以及能耗组成任务分配多目标函数;在约束条件下利用长短期记忆神经网络求解任务分配最优方案,完成容器云队列在线任务动态分配。实验结果表明,本文分配方案的分配合理性达到0.925,资源均衡度达到10.255,最长队列长度为10,最大能耗值为5000 W,分配合理性、资源均衡度、任务处理效率均得到改善,分配方案更加合理。     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

一种基于两级DAG模型的MapReduce工作流异构调度算法

MapReduce编程模型被广泛应用于大数据处理平台,而一个有效的任务调度算法对模型的运行效率至关重要。将MapReduce工作流的Map和Reduce阶段分别拆解为若干个有先后序限定关系的作业,每个作业再拆解为多个任务。之后基于计算集群的可用资源和任务异构性,构建面向作业和任务的2级有向无环图(DAG)模型,同时提出基于2级优先级排序的异构调度算法2-MRHS。算法的第1阶段进行优先级排序,即对作业和任务分别进行优先权值计算,再汇总得到任务的调度队列;第2阶段进行任务分配,即基于最快完成时间将每个任务所包含的数据块子任务分配给最适合的计算结点。采用大批量随机生成的DAG模型进行实验,结果表明与其他相关算法相比,本文算法有更短的调度长度(makespan)且更加稳定。     

微小卫星集群协同观测构形调整规划

以微小卫星集群实现小行星探测为背景,研究局部信息交互的空间目标观测任务构形调整.针对难以直接求取集群构形调整的全局最优解问题,利用通信协调图,将全局协调决策分解成多个局部求解问题,并引入强化学习机制实现求解.针对集群全局协调决策问题,通过设计基于Max-plus算法的全局协调决策算法来实现全局协作;针对单星局部优化问题,设计基于神经网络的局部Q学习算法来实现单星动作调整规划.仿真结果表明,本文所提的协作规划算法能自主有效地将集群调整至期望构形,实现协同观测任务.     

基于任务分配和数据集副本的科学工作流数据布局

云环境下科学工作流的数据布局成为当前工作流研究中的一个热点问题,对科学工作流中任务和数据之间多对多关系进行分析,可以发现不同数据布局方案在数据传输上的费用各不相同,在很大程度上影响工作流的运行成本。为降低科学工作流数据集传输费用,提出一种基于任务分配和数据集副本的科学工作流数据布局方法。该方法从任务分配开始,在定量计算任务依赖度的基础上进行任务分配,根据分配结果给出一个基于数据集副本的两阶段数据布局方法,以实现科学工作流运行中传输费用的优化。实例结果表明,与工作流层方法相比,该方法可以有效降低科学工作流的运行成本。     

基于多微云协作的计算任务卸载

针对多微云计算模式下计算任务卸载过程复杂、任务响应时间长的问题,构建面向多微云协作的计算任务卸载模型,并提出加权自适应惯性权重的粒子群优化（WAIW-PSO）算法,快速求解最优卸载策略。首先,对移动终端-微云-远程云的任务执行过程进行建模;其次,考虑多用户对计算资源的竞争,构建基于多微云协作的任务卸载模型;最后,针对求解最佳任务卸载策略复杂度过高的情况,提出WAIW-PSO算法求解卸载问题。仿真实验结果表明,与标准粒子群优化（PSO）算法以及基于高斯函数递减惯性权重的粒子群优化（GDIWPSO）算法相比,WAIW-PSO算法可以根据进化代数和个体适应度综合调整惯性权重,寻优能力较强,求解最优卸载策略的时间最短;在不同设备数、任务数等情况下选择不同任务卸载策略进行对比实验的结果表明,基于WAIW-PSO算法的卸载策略可以明显缩短任务总完成时间。     

A hybrid evolutionary approach for heterogeneous multiprocessor scheduling

This article investigates the assignment of tasks with interdependencies in a heterogeneous multiprocessor environment; specific to this problem, task execution time varies depending on the nature of the tasks as well as with the processing element assigned. The solution to this heterogeneous multiprocessor scheduling problem involves the optimization of complete task assignments and processing order between the assigned processors to arrive at a minimum makespan, subject to a precedence constraint. To solve an NP-hard combinatorial optimization problem, as is typified by this problem, this paper presents a hybrid evolutionary algorithm that incorporates two local search heuristics, which exploit the intrinsic structure of the solution, as well as through the use of specialized genetic operators to promote exploration of the search space. The effectiveness and contribution of the proposed features are subsequently validated on a set of benchmark problems characterized by different degrees of communication times, task, and processor heterogeneities. Preliminary results from simulations demonstrate the effectiveness of the proposed algorithm in finding useful schedule sets based on the set of new benchmark problems.     

实时异构系统的动态分批优化调度算法

提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.     

Maximal profit service task partition and distribution in computer grid

The paper considers grid computing systems in which the resource management systems (RMSs) can divide service tasks into execution blocks (EBs) and send these blocks to different resources. The service price is determined as a function of time elapsed till the service task completion according to a fixed tariff. The service time distribution depends on the assignment of the execution blocks to the resources as well as on the reliability of these resources. The cost of service depends on the resources used for its execution and is proportional to the time when the resources perform the execution blocks assigned to them. The optimal task partition and distribution should maximize the provider’s profit, which is equal to the difference between the expected service price and its cost for the provider. The paper suggests an algorithm for solving this optimization problem. The algorithm is based on the universal generating function technique and on the evolutionary optimization approach. Illustrative examples are presented.     

智能仓储中的多机器人调度方法

近年来,传统仓储系统已满足不了日益增长的订单需求并已渐渐向智能仓储转变。针对智能仓储中移动机器人的调度问题,以移动机器人执行任务时的转向次数、路程代价、最大任务等待时间为优化目标,提出一种兼顾任务分配和路径规划的调度算法。算法采用遗传算法进行任务分配,同时以多个移动机器人为目标进行任务分配,保证每个机器人分配到的任务没有重复。然后采用Q-learning算法对机器人分配到的任务进行路径规划,根据转向次数和路程代价约束路径,对于路径转向和每一步可行的动作均设有惩罚值,最终形成一条转向次数少、行程较短的路径。通过将该算法与其他算法进行对比,证实了该算法的有效性。