数据驱动的多星任务网络预测调度算法

多星任务调度是具有NP-hard特性的优化问题,随着卫星资源规模和任务需求规模的双重增长,传统调度方法求解效率不高.在轨卫星在常年运行过程中积累了丰富的调度数据.针对大规模多星任务调度场景,建立多星多波束任务调度模型,并提出数据驱动的多星任务网络预测调度算法对其求解.以分割的思想,实现多星场景下任务可调度性预测.从历史调度数据中,提取设定的3个静态特征和5个动态特征,构建并训练预测网络,预测任务被不同卫星完成的概率,并以冲突避免、负载均衡等为原则,得到初始任务和资源卫星的分配方案.进一步设计双链结构的进化算法,以双链编码形式表征上述关系,配合设计的交叉、修复等进化算子,优化初始方案中的任务序列与资源分配关系,输出最终任务调度方案.仿真结果表明,与改进蚁群算法、混合遗传算法和数据驱动并行调度算法相比,所提出算法在运行时间、方案收益和卫星负载均衡3方面均有较好的表现.     

协同任务调度构架模型及关键算法研究

为提高协同工作平台服务系统的协同任务调度的柔性及系统的平台伸缩性,需要从调度过程,软件结构和调度算法等方面进行研究.首先提出协同任务调度软件构架模型,采用多种软件优化方法对构架模型进行优化.然后提出驱动协 同任务调度的过程元模型.最后,研究协同任务调度中的成员指派过程的关键算法,给出算法的形式化描述,并对算法效果进行验证.该软件构架和算法在实际应用中取得良好效果.     

混合算法在网格任务调度中的应用研究

研究网格任务优化调度问题,针对需求的复杂和网格系统具有异构性和动态性,导致网络任务调度过程相当困难.传统调度算法调度效率低、资源负载不平衡.为了提高任务调度效率,降低资源负载不平衡性,提出一种混合的网格任务调度优化算法.首先采用遗传算法全局搜索能力快速形成初始解,然后将遗传算法的调度结果作为蚁群算法的初始信息素分布,最后利用蚁群算法所正反馈性机制迅速地形成任务调度的最优解.仿真结果表明,混合算法减少网格任务调度系统任务完成时间,提高了任务调度效率,为网格设计提供了依据.     

基于面向任务模型的陆基卫星测控资源克隆选择优化调度

建立了面向任务的陆基卫星测控资源优化调度数学模型,与已有数学模型不同的是,该模型约束同一测控请求同一时刻只被一个可见陆基测控设备测控,为调度算法调度陆基测控设备完成更多的测控任务提供可能.基于此模型提出了基于面向任务模型的陆基卫星测控资源克隆选择优化调度算法(Clonal Selection land-based Sat-ellite TT&C Resources Scheduling Algorithm based on the mission oriented model,CS_STT&LCRSA),并从理论上证明了算法的收敛性.算法中采用能表示各测控请求时间先后及其与陆基测控设备关系的矩阵编码方式表示种群中的抗体;并针对该编码方式设计了相应的强约束满足算子,保证操作后的抗体满足强约束条件.在5颗同步卫星和30、40、50颗近地卫星请求测控的情况下,分别仿真了10组不同任务.对比实验表明,新建的数学模型可使调度算法更好地利用陆基测控设备;CS_STT&CRSA有更强的搜索能力和约束解决能力,能调度测控资源完成更多的测控任务,它的性能也更加稳定.     

一种启发式与/或优先约束任务调度算法

系统描述了与或网模型及与或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与或优先约束任务调度最小完成时间问题.仿真结果表明,该算法在降低算法复杂度的同时较其它相关算法具有更好的调度性能,从而证明在实时优先约束任务调度中引入图优化的理论是解决优先约束任务调度问题的一个有效途径.     

考虑邻域结构动态调整的多星应急调度算法

实际应用中的卫星调度方案往往受到外界因素的影响,例如电磁干扰、卫星失效、云层遮挡以及新任务的动态到达等,需要在短时间内对原始调度方案进行调整并生成新的调度方案,以保证卫星系统的稳定性.对此,考虑新任务到达情况下的卫星应急调度,建立多星协同应急调度的整数规划模型,并提出一种基于动态邻域结构的卫星应急调度算法(satellite emergency scheduling algorithm based on dynamic neighborhood, SESA-DN).设计多种类型的邻域结构以及动态的邻域选择策略,能够根据任务完成情况进行有效反馈,通过对应急任务的插入与替换生成卫星应急调度方案;同时,构建多星应急调度场景,通过大量仿真实验将SESA-DN算法与多种对比算法进行比较.实验结果表明, SESA-DN算法的稳定性优于对比算法,对于多星协同动态调度问题具有很好的适用性.     

基于GRASP算法的多成像卫星协同观测调度

针对摘要多成像卫星协同观测调度问题,具有观测任务的时间窗口、卫星存储及能量等约束,是一个NP难的组合优化问题。建立了多成像卫星协同观测调度模型,采用贪婪随机自适应搜索算法(GRASP)对问题模型进行求解,并且对基本的GRASP算法做出了一定的改进,在其初始解的构造阶段设计了定长受限候选列表和变长受限候选列表两种策略,在邻域搜索阶段结合模拟退火算法来搜索更好的解。仿真实例表明,该算法在解决成像卫星任务调度问题时是有效的。     

卫星自主运行任务调度问题的优化算法

针对卫星自主运行任务调度问题的特点,设计了一种基于遗传的新的调度算法。以卫星对地拍照任务作为仿真实例,对算法的编码方式和解码规则、初始群体的产生方法、适值函数、遗传算子进行了详细的描述。计算结果表明,同精确算法相比,该调度算法能很好地解决卫星自主运行任务调度问题。     

基于双层优先级的中继卫星系统任务调度算法

中继卫星系统在天基信息网中起着桥梁的作用。为充分利用卫星资源以提供快速可靠的数据中继服务,需要对高价值、高紧迫性的任务开展调度方法研究。首先,在分析中继卫星系统任务与资源的基础上,建立了多任务、多资源的调度模型。而后,提出了任务调度优先级和时间窗口选择优先级模型,并在此基础上提出了一种基于双层优先级的中继卫星系统调度算法。最后,根据算法在仿真算例中的应用可见：相比对照算法,基于双层优先级的调度算法更有利于满足高价值、高紧迫性任务的执行条件,从而提高了任务成功率和调度综合收益。     

航天器任务调度模型、算法与通用求解技术综述

针对航天器任务调度大规模、复杂化的新常态和灵活组网、快速响应的新要求, 综述了航天器任务调度模型、算法与通用求解技术的发展现状. 首先, 基于遥感卫星、中继通信卫星、导航卫星和航天测控等航天器任务, 从任务排序模型和时间窗口分配模型两个角度出发, 揭示了不同航天器任务调度模型的决策形式和共性特征, 阐明提升模型兼容性、适用性的必要性. 其次, 基于启发式算法、精确求解算法和元启发式算法, 探讨了航天器任务调度算法的适用模型与编码特色, 指明“算法?模型”解耦、算法深度融合的重要性. 在此基础上, 介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等航天器任务调度通用求解技术的模型、算法与主要功能, 说明我国自主研发通用求解技术的必要性和新的应用思路. 最后, 指出了开发航天器任务调度统一化建模语言、打造算法库与测试集等未来航天器任务调度研究的新方向.     

InSAR双星编队测绘卫星任务规划方法研究

针对双星编队干涉合成孔径雷达(Interferometric Synthetic Aperture Radar, InSAR)测绘任务的特点,考虑双星编队卫星平台的约束条件,采用多目标优化和基于优先级的遗传优化算法,实现了双星编队任务规划的各个关键步骤的设计,并对测绘任务进行了系统仿真,求取了测绘任务规划结果,最终获得了任务规划的最优解。经过与贪婪优化算法仿真结果对比分析,采用的基于优先级的遗传优化任务调度算法在双星编队卫星测绘任务优化问题求解方法方面具备明显的优势,卫星系统资源分配效能达到最优,对卫星资源的合理分配起到了关键作用。     

基于多目标数学规划的网络多源数据调度仿真

传统的目标网络多源数据调度方法通常以时间或费用为单一调度优化目标,无法实现任务完成时间以及任务执行成本之间的均衡,造成系统资源利用率较低。针对上述问题,提出一种基于多目标数学规划的网络多源数据调度方法。使用DAG构建网络多源数据流,确定多源数据调度任务模型的信任关系,以任务完成时间、任务完成成本、资源利用率为优化目标,建立多目标调度任务模型。对模型进行求解,在遗传算法变异操作中加入粒子群算法,对数据变异的方向与幅度进行调整,完成网络多源数据调度。仿真证明,所提方法相较于传统方法,在多源数据的调度上成本更低、资源利用率更高,并且调度任务目标完成时间更短。     

面向多星任务规划问题的改进遗传算法

卫星数量的快速增加为管控卫星的工作增加了很大的难度,如何有效地进行任务规划,有效管理卫星资源,成为了卫星领域的一个重要问题.针对此问题,本文构建了多星任务规划的数学模型,将最大化任务收益作为优化目标.本文分析了问题的难点并提出了一种包含两种优化策略的改进遗传算法,包括全局优化和局部优化两部分.全局优化和局部优化根据种群改进情况进行自适应切换.通过两种优化方法的结合可以提升任务规划的效果.本文还提出了一种任务规划算法,用于为改进遗传算法得到的任务序列选择合适的任务执行时间.仿真实验证明本文提出的改进遗传算法可以很好地解决多星任务规划问题,与对比算法相比可以得到更优的规划结果.改进遗传算法有很好的工程应用前景.     

A two-phase scheduling method with the consideration of task clustering for earth observing satellites

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems. Although extensive scheduling algorithms have been proposed for the satellite observation scheduling problem (SOSP), the task clustering strategy has not been taken into account up to now. This paper presents a novel two-phase based scheduling method with the consideration of task clustering for solving SOSP. This method comprises two phases: a task clustering phase and a task scheduling phase. In the task clustering phase, we construct a task clustering graph model and use an improved minimum clique partition algorithm to obtain cluster-tasks. In the task scheduling phase, based on overall tasks and obtained cluster-tasks, we construct an acyclic directed graph model and utilize a hybrid ant colony optimization coming with a mechanism of local search, called ACO–LS, to produce optimal or near optimal schedules. Extensive experimental simulations demonstrate the efficiency of the proposed scheduling method.     

基于作业链的泊位与岸桥协同调度研究

针对泊位与岸桥协同调度问题,引入"链式优化"思路,用作业链的方法分析集装箱装卸作业过程,首先将泊位计划作为开始链单元,采用资源节点优化策略进行分析,以最小化船舶在港总成本为目标建立模型;然后将岸桥卸船作业作为结束链单元,采用任务节点优化策略进行分析,以最小化岸桥最大完工时间为目标建立模型.考虑到作业链的整体性能,设计嵌...     

基于改进烟花算法的密集任务成像卫星调度方法

传统卫星调度模型一般比较简单,当问题规模较大、任务比较集中时,往往会出现任务之间相互排斥,任务收益较低等缺点。针对这个问题,提出一种基于改进烟花算法（IFWA）的密集任务成像卫星调度方法。该方法在分析密集任务处理及成像卫星观测特点的基础上,首先对任务进行合成约束分析,然后基于合成任务综合考虑成像卫星可观测时间、任务间姿态调整时间、成像卫星能量和容量等约束因素,建立基于任务合成的多星密集任务调度约束满足问题（CSP）模型,最后改进烟花算法对该模型进行求解,利用精英选择策略在保证种群多样性同时加快了算法的收敛,得到较优的卫星调度方案。仿真结果表明该模型相比没有考虑任务合成因素,收益平均增加30%~35%,改进算法后效率上提升32%~45%,有效保证了调度方案的可行性和有效性。     

动态储位分配策略下仓储作业能耗优化调度

针对堆垛机式自动化立体仓库能耗优化任务调度问题,提出了一种动态储位分配策略下的任务调度集成优化方法。该策略允许在当前任务执行批次内重用拣货产生的空库位,产生了任务顺序约束;并结合不同运动状态下堆垛机的运行时间计算差异,建立了复合指令下以堆垛机任务总能耗最低为目标的调度模型。依据模型的特点,提出了一种改进帝国竞争算法进行求解。该算法通过设置校正机制使优化解能够满足任务顺序约束,并引入外来种群入侵的概念来避免算法陷入“早熟”。最后通过两组数据对提出的任务调度算法进行了验证,实验结果表明,改进算法在能耗和任务执行效率方面优于其他方法,能够有效减少堆垛机作业过程能耗,提升作业效率。     

粒子群优化的改进机场车辆调度模型研究

随着航空事业的迅猛发展,机场车辆调度的安全性和时效性地位已日趋突显,传统的机场车辆调度采取First in first out策略,该策略算法简易,便于实施,缺陷是全部调度的分组被相同对待,无法为实时要求较高的业务提供时延保证,算法也不具有公正性。提出了一种基于粒子群优化的改进机场车辆调度模型,把粒子群已经搜索到的全局最优地点视为一个特殊的粒子,采用梯度降低策略寻优该粒子,全局寻优特性和梯度降低算法的邻域寻优特性相融合,以提升粒子群优化算法的全局寻优效率,减少机场车辆调度计算的时间。仿真实验表明：粒子群优化的改进机场车辆调度模型,能够减少传统调度方法的寻优轮换次数,进而缩短优化调度时间,有效缓解空中堵塞造成的资源浪费。