面向区域的电子侦察卫星规划系统设计与实现

电子侦察卫星对区域目标的覆盖侦察在反恐及海上搜救等领域发挥着极其重要的作用。针对电子侦察卫星区域覆盖探测需求,综合考虑各种星地资源使用约束,提出了一种面向区域覆盖的电子侦察卫星多目标规划方法,并设计实现了相应的规划仿真系统。对问题建模进行了深入分析,设计了系统的组成结构及运行流程,并详细介绍了各功能模块中的关键技术,包括基于多目标进化机制的侦察序列求解算法和基于并行车间调度模型的数传序列求解算法。最后给出了一个应用实例及仿真规划结果,从侦察规划和数传规划两方面验证了系统的有效性与适应性。该系统的运行效果已在实际项目中得到检验。     

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

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

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

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

多类扰动下电子侦察卫星动态调度问题研究

针对电子侦察卫星在执行初始侦察计划过程中各种扰动发生的情况,分析研究各类扰动的特点,建立资源和任务之间的优先映射关系,引入扰动测度来度量动态调度规划结果与原规划结果之间的变化程度;以最大化完成任务优先级之和,以及扰动发生后对原始计划调整最小为目标,建立了具有两级优化目标的动态约束满足模型,提出动态调度的启发式信息计算方法及基于启发式信息的动态调度方法,通过实例仿真,表明该扰动测度和链式效应影响计算方法,以及模型和算法的可行性,对解决实际问题具有一定理论意义和现实意义。     

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

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

星地一体成像侦察任务规划组合求解方法

成像侦察任务流的航天资源任务规划问题是将有限的航天资源分配给需要侦察的不同目标,最大化满足任务需求.采取了星地一体任务规划思路进行问题建模与求解.提出星地一体虚拟资源聚合模型和算法,并在此基础上,给出了星地一体的虚拟资源冲突检测与消解方法,提出了星地一体任务规划模型的模型分解与组合求解方法,针对分解后的主问题模型给出了一种适应可变冲突约束的遗传算法;针对子问题模型给出了一种基于时间序列排序的任务调度方法,并对上述两种算法进行了设计与实现;最后,结合试验案例进行验证.     

基于禁忌搜索算法测地卫星任务调度研究

研究测地卫星调度问题,它是一个复杂的组合优化问题,涉及多个卫星,大量的任务与约束限制,何时和如何执行每项任务。分析了问题的主要约束,在合理的假设基础上建立了带有时间窗口多资源调度问题模型,提出一种改进的禁忌搜索算法求解该模型。用实例对模型和算法进行了验证,并将结果与动态规划方法求解结果比较分析,结果表明模型和算法是有效的。     

基于差分进化的临近空间探测资源调度

针对临近空间预警探测平台的协同资源调度问题,根据临近空间探测资源与探测任务的特点,考虑多种实际约束条件,构建临近空间探测资源的优化调度模型。根据该模型规模大、求解复杂的情况,提出一种基于种群灾变的自适应差分进化算法求解模型。仿真实验结果表明,该算法相比传统算法收敛速度更快、寻优能力更强。     

基于优先规则的空间资源约束项目调度算法

任务组占用空间资源项目调度问题需满足组内任务的序关系和人力、设备等常规资源约束,以及空间资源这一特殊资源的约束,同时任务组之间也需满足上述约束,使得该调度问题异常复杂。以船舶建造分段制造问题为背景,建立任务组占用空间资源受限的项目调度问题数学模型,基于并行调度生成方案提出基于优先规则的启发式调度算法,实现对该调度问题的综合求解。实例测试结果表明了该算法的正解性和有效性。     

遥感卫星数据预处理系统复杂任务调度模型研究与实现

针对遥感卫星数据预处理系统同时对多卫星数据处理任务进行调度时,因资源分配不合理,导致计算资源浪费、系统吞吐量低、无法满足卫星数据时效性要求的问题,提出了一种基于预处理任务性能及预处理系统工作流特性的调度模型。该模型通过研究预处理任务算法的一般特征,对不同资源分配情况下的任务执行时间进行预估,并根据预处理任务工作流对卫星数据产品所需总时间进行预估;在此基础上,采用基于任务时效性和系统资源利用率的二次资源动态分配算法对预处理任务进行调度。实验结果表明,该调度模型在满足多卫星数据处理的时效性要求的同时,合理地减小调度过程中存在的资源浪费,提高了系统的吞吐量。     

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

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

基于贪心算法的科学卫星下行传输规划

本文针对多星、多站、变速率、大数据量的科学卫星数据下行传输规划问题,在开机时间约束条件下,考虑任务权重,建立了多卫星规划调度模型,提出了基于贪心算法的求解模型,并以两颗科学卫星的调度问题为例,对模型和算法进行了验证.     

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

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

A CSP approach for the network of product lifecycle constraints consistency in a collaborative design context

In this paper, we are considering that the design process can be modelled in the form of a constraint satisfaction problem (CSP). CSP modelling or resolution has proved its efficiency within the framework of single-designer design. We propose to extend the functions of CSP to the context of multi-concept design of the same artefact. We define CoCSP as cooperative constraint satisfaction problem including the actors of the design problem. We are presenting the operating principles of an algorithm for the real-time management of design decisions, based on a model described in the form of a CoCSP for the integration of supply-chain constraints. This algorithm enables the number of design decisions rejected at a given moment in design to be kept to a minimum. The algorithm forms the core of a prototype for an unsupervised, generic constraint-based collaborative design system. Our aim is to produce a platform centred on the notion of constraints that will enable a product design problem to be modelled and solved by integrating supply-chain constraints as far upstream as possible.     

多维动态规划在对地观测卫星调度中的应用

对地观测卫星调度问题是指如何利用有限卫星资源,在时间、空间等多约束条件下提高对地观测任务执行效率,是一个多约束条件下的目标满足问题.多维动态规划是针对多维约束任务将有限资源进行合理分配、高效调度的有效方法.它以缩短任务完成时间为目标,通过先求解一系列子问题,再处理子问题间关系求得问题最终解,避免了计算的复杂性,又满足了时效性要求.针对卫星对地观测任务约束变量多的特点,将多维动态规划应用到对地观测卫星调度问题中,是解决该问题在时效性要求条件下的有效方法,其可行性通过想定任务在文章中得到证明.     

On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.     

Hybrid tractability of valued constraint problems

The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.