贪婪搜索算法在卫星调度中的应用

针对采用天气预报的滞后云层进行卫星调度影响观测图像质量和观测收益的问题,提出一种获取实时云层的数学模型,并基于此构建考虑实时变换云层的敏捷观测卫星（AEOS）调度模型。由于贪婪搜索算法（GSA）具有局部优化的特性,能够充分考虑卫星观测的云层和有限存储资源等约束,研究了GSA在该卫星调度问题中的应用。首先,GSA优先考虑观测任务的云层遮挡,并根据云层遮挡大小,计算待观测任务的图像质量,将之排序选择待观测的任务;其次,结合任务的大小、截止时间和卫星的存储资源约束,选择能够给观测收益带来最大化的任务;最后,进行观测和任务传送。仿真实验表明,在任务数为100的情况下,采用GSA进行卫星调度的任务收益比常用于卫星调度的动态规划算法（DPA）所获得任务收益提高了14.82%,比局部搜索算法（LSA）所获得任务收益提高了10.32%,并且同等条件下,采用GSA得到的观测图像的质量比其他两种方法得到的图像质量更高。实验结果表明,GSA在实际卫星调度中,能够有效地提高图像观测质量和任务观测收益。     

敏捷凝视卫星密集点目标聚类与最优观测规划

针对敏捷凝视卫星密集点目标观测规划问题,提出一种快速观测任务聚类策略和启发式蚁群优化算法.首先,针对敏捷凝视卫星视场范围特点,提出基于顶点度的团划分算法,解决密集点观测任务聚类问题,形成系列团观测目标,有效提高观测效率;其次,为得到最优团目标观测序列,考虑目标可见时间窗口约束以及卫星敏捷机动能力约束,构建基于多目标观测收益和姿态机动能耗的性能指标,实现能量高效的任务规划;再次,为克服传统蚁群算法易陷入局部极小值和收敛较慢的缺点,设计一种同时考虑目标点优先级、目标可见时间窗口、目标之间卫星姿态转换时间等因素的启发式蚁群算法;最后,选取大规模密集地面目标验证所提出算法的可行性和高效性.     

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

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

成像卫星星地联合成像调度

成像卫星星地联合调度问题,涉及调度对象众多,约束条件复杂,需要考虑任务的观测、回传2个过程,是一个具有两层时间窗口约束的双层优化问题,统一建模困难。根据问题的特点,采用基于阶段优化的方式,降低了问题的复杂性。把问题分为观测调度阶段和数据回传调度阶段,分别给出了优化目标和约束条件,建立了基于阶段优化的成像卫星星地联合调度模型,实现了从任务观测到数据回传的全过程调度。仿真实例表明,该方法能够有效解决多星多站的协同任务调度问题。     

基于贪婪算法成像侦察卫星调度方法研究

成像侦察卫星的调度问题需要考虑大量互相联系的约束条件,实现全面调度的难度比较大,特别是在作战的情况下,很难满足快速战略决策的要求,而且各种干扰因素将会对卫星的状态产生影响,需要优越的初始调度方案作为基础.针对以上提出的实际问题,首先对成像侦查卫星约束条件进行分析,在简单假设的基础上对问题进行描述,建立卫星调度的约束模型,基于贪婪算法原理,通过软件实现调度模型求解,得到成像侦查卫星的快速调度方案,为卫星任务状态变化的二次调度和满足快速战略决策提供比较令人满意的调度基础解.     

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

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

卫星成像规划调度系统中的可视化决策支持研究与实现

本文提出了一种成像卫星规划与调度的可视化决策支持方法。该方法基于多目标进化算法和地理信息系统技术，能够在考虑多目标准则、多约束的条件下对成像卫星的成像方案进行优化，并通过可视化技术进行成像方案的决策辅助，很好地解决了卫星规划调度优化方案制定的问题。     

电子侦察卫星动态调度问题的快速启发式算法

卫星电子侦察中针对动态突发事件重新制定侦察计划是侦察任务规划所要解决的基本问题.分析导致动态调度的扰动因素,把不同扰动下的动态调度问题归结为一类复杂约束下的任务插入问题.建立混合整数规划模型,提出快速启发式任务插入算法(含三个基本算法--直接插入任务算法、移位插入任务算法和替换插入任务算法);基于初始调度方案的优良特性,极大降低动态调度复杂性.仿真实验表明:该算法能有效解决电子侦察卫星动态调度问题.     

卫星任务规划可视化仿真系统设计与实现

解决卫星任务规划方案正确性、可靠性问题的有效途径是建立可视化仿真分析环境,研究多星多地面站任务规划问题,设计了成像需求约束图模型,利用任务规划调度算法进行优化分析生成最优解决方案,同时研究利用基于MapX的地理信息系统功能,设计实现了卫星任务规划可视化仿真系统,实现了二维视景仿真、方案动作仿真以及可视化决策支持等功能.该系统为卫星任务规划的可视化决策、可视化仿真提供了基础,确保了其正确、可靠性.     

基于模糊偏好的多目标成像卫星调度方法研究

不确定条件下的成像卫星调度问题是一个多目标优化问题。借鉴连续函数的鲁棒性优化思想,提出了一种基于邻域的鲁棒性指标,考虑多种约束条件,建立了多目标成像卫星调度模型。在考虑目标间偏好的情况下,提出了一种基于模糊偏好的多目标遗传算法。实例研究表明,该模型和算法能够有效地解决不确定条件下的成像卫星调度问题。     

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

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

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

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

一种解决卫星网络通信冲突的调度算法

在卫星网络中多颗卫星同时对一颗卫星进行通信申请会产生任务冲突问题。为此,提出一种基于动态优先级的调度算法。建立卫星通信任务模型,利用任务执行紧迫性表达任务截止期与空余时间这2个时间约束,并根据卫星网络的特点,通过调整参数p控制紧迫性对任务优先级的影响程度。利用STK场景建立冲突模型进行仿真实验,结果证明该算法的任务完成率相比FCFS算法提高了3.9%。     

移动边缘计算中基于Lyapunov的任务卸载与资源分配算法

移动边缘计算（MEC）通过将计算和存储资源部署在无线网络边缘,使得用户终端可将计算任务卸载到边缘服务器进行处理,从而缓解终端设备资源受限与高性能任务处理需求之间的冲突。但随着任务卸载规模的不断增加,执行任务所产生的功耗急剧上升,严重影响了MEC系统的收益。建立任务队列动态调度模型,以队列上溢概率为约束构建最大化系统平均收益的资源优化模型。考虑到资源优化问题为不同时隙下的耦合问题,运用Lyapunov优化理论设计一种基于单时隙的资源分配算法,将优化问题转化为用户本地计算资源分配、功率和带宽资源分配以及MEC服务器计算资源分配3个子问题并分别进行求解。仿真结果表明,该算法在满足用户QoS需求的同时能够有效提高MEC系统的时间平均收益。     

卫星数传应急任务调度模型

在卫星数传调度研究中,待调度方案形成后,通常不做任务调整,但实际中会有应急情况出现。为解决该问题,提出一种任务调度模型。将卫星数传任务分为常管任务和应急任务,建立应急任务模型,设计其调度算法,具体包括调度顺序的确定、初始调度方案的调整以及调度流程。实验结果表明,该算法能保证应急任务的优先级之和最大,同时保持原方案的稳定性。     

侦察卫星探测资源调度研究

侦察卫星探测资源调度是一类基于约束满足的优化问题。对卫星探测资源和探测任务的特点进行分析,在此基础上构建卫星探测资源调度的目标函数和约束条件,利用约束满足问题的建模思想对该调度问题进行建模。针对约束满足模型规模大、求解复杂的情况,结合卫星探测资源调度问题的特征,提出一种基于启发式禁忌搜索算法的模型求解方法,并通过仿真算例进行说明与分析。该调度模型和算法充分考虑了星载资源与对应任务的特点,尽量回避假设与简化条件的提出,具有较好的适用性,将为侦察与预警卫星网络任务规划与资源调度的研究奠定基础。     

云计算平台中非定期任务并行调度仿真

由于云计算平台的动态不确定性和非定期任务调度本身的复杂性,使得非定期任务调度过程中的耗时长和负载不均等问题很难得到有效解决。针对上述问题,提出一种非定期任务并行调度方法,并应用到云计算中。通过多方面考虑云平台客户非定期任务的截止时间底线、调度估算等并行调度约束条件和各种可用资源的性能参数,对非定期任务调度的多目标约束条件进行量化建模。基于建模生成的隶属度函数将非定期任务多目标约束的调度优化问题转变成单一目标约束问题,采用模拟退火算法对该问题进行求解,最终实现对非定期任务的并行调度。分析实验结果可知,与传统方法相比,所提方法能够有效减少非定期任务的传输时间,并且能够均衡节点负载,表明所提方法具有有效性。     

提高卫星服务寿命的任务规划方法研究

基于组网卫星协同工作规划可提高复杂任务处理的基础上,本文探索降低规划风险,提高卫星服务寿命的卫星任务规划方法.从提高卫星服务寿命角度,建立用于描述资源使用期望的目标规划模型;建立卫星任务规划模型,在任务方案与资源使用中考虑了规划风险要素,并将资源使用目标模型引入到任务规划模型中,以期在规划中同时优化卫星服务寿命要素;基于邻域贪心扩展改善遗传禁忌求解算法,并运用分布并行技术提高工程实用性;利用STK提供基础仿真数据,对模型与算法进行了验证.     

A hybrid instance-intensive workflow scheduling method in private cloud environment

Aiming to solve the problem of instance-intensive workflow scheduling in private cloud environment, this paper first formulates a scheduling optimization model considering the communication time between tasks. The objective of this model is to minimize the execution time of all workflow instances. Then, a hybrid scheduling method based on the batch strategy and an improved genetic algorithm termed fragmentation based genetic algorithm is proposed according to the characters of instance-intensive cloud workflow, where task priority dispatching rules are also taken into account. Simulations are conducted to compare the proposed method with the canonical genetic algorithm and two heuristic algorithms. Our simulation results demonstrate that the proposed method can considerably enhance the search efficiency of the genetic algorithm and is able to considerably outperform the compared algorithms, in particular when the number of workflow instances is high and the computational resource available for optimization is limited.