应急事件中瓶颈环节的实时优化调度

应急事件中的资源优化调度处于复杂动态的环境中,受到各种随机因素的影响,使得问题求解更加困难。约束理论指出瓶颈决定了整个系统的性能,通过对瓶颈环节的实时调度可以简化问题。用三元组α/β/γ方法分析了应急事件中瓶颈环节优化调度问题的特征,建立了对应的数学模型。运用基于任务的实时调度策略与包含复合动态分派规则的启发式算法进行问题求解。通过仿真结果验证算法的优越性和可行性。     

多星成像调度问题基于分解的优化算法

提出了一种求解多星成像调度问题的基于分解的优化算法,将问题分解为任务分配主问题与单星成像调度子问题.任务分配主问题生成不同卫星的任务分配方案,单星成像调度子问题则根据分配的任务进行优化,生成每颗卫星的成像调度方案.采用自适应的蚁群算法求解任务分配主问题,通过自适应参数调整策略及信息素平滑策略,实现全局搜索和快速收敛间的平衡.采用启发式算法及快速模拟退火算法求解单星成像调度子问题,通过综合多颗卫星的调度结果, 可以对任务分配方案进行评价,引导蚁群算法搜索优化的任务分配方案,最终得到多颗卫星的成像调度方案. 大规模测试算例验证了算法的效率.     

面向应急成像观测任务的多星协同调度方法

针对应急条件下的成像观测任务,设计了多星协同调度框架,将多星协同调度问题分解为任务排序主问题和资源匹配子问题。分析了多星协同调度中的主要约束条件,以任务收益为优化目标构建问题的约束满足模型,并应用改进粒子群优化算法进行求解。详细介绍了算法中的编码、解码、移动、变异等操作,给出算法时间复杂度的计算公式。通过仿真实验,对算法的有效性进行了验证。     

基于任务合成的对地观测卫星应急调度方法

针对应急条件下对地观测任务时敏度高、动态性强的特点,提出了基于任务动态合成的多星应急调度方法。首先,建立了多星动态应急调度数学规划模型。然后,提出了任务动态合成(dynamic merging,DM)策略,并设计了候选合成任务集合构建(candidate merging task set establishment, CMTSE)算法。最后,提出了基于任务动态合成的多星动态应急调度(dynamic merging based dynamic emergency scheduling, DM DES)算法。为验证DM DES算法的有效性,通过大量仿真实验将DM DES与基于迭代修复的启发式算法(repair based heuristic algorithm, RBHA)和不考虑任务合成的动态应急调度(dynamic emergency scheduling, DES)算法进行比较。实验结果表明,DM DES算法能有效提高调度质量,适用于多星动态应急调度。     

带有缓冲区的资源受限调度问题的滚动时域求解算法

研究带有缓冲区的资源受限调度问题,设计了两种使用滚动时域策略的启发式算法TWBA和FWBA,通过依次处理一定量任务,尽可能使得调度所产生的费用最小.为了评估算法性能,进行了大量模拟研究,在不同条件下找出相应的最优的处理周期或者是最优决策时刻,仿真结果表明了新算法在应用中有较好的性能,并且得到比在线算法更优的调度结果.     

动态单机调度的一种滚动时域策略及全局性能分析

针对全局信息不完全的一种单机的动态调度模型,设计了局部调度子问题带终端惩罚函数的滚动调度策略,并对这种滚动调度策略下的全局性能进行了分析.通过对未知工件按FIFO规则进行虚拟调度,对滚动调度进程中的全局性能进行评估,证明了在所给滚动调度策略下,随着工件信息的逐步获取,全局调度中的虚拟调度逐步变为已知调度,并经过滚动局部调度而部分实现,决策时刻向前推进,对全局性能指标的估计越来越接近将实现的实际值,逐步实现的全局调度性能相对历次的估计值不断改善.终端罚函数滚动调度策略可以保证滚动调度进程中全局性能的稳定性,当工件到达较快时,文中的滚动调度策略更有优势.     

任务驱动的应急资源集成方式与组织过程建模

通过应急平台实现应急组织资源协作调配是当前应急工作的重要方法.根据突发事件情景任务,快速组建与应急任务功能契合的应急资源组织体系,是保证应急管理平台的辅助决策有效性的关键.本文在对应急管理平台资源集成模式分析的基础上,建立了任务驱动的应急平台资源集成框架,对任务驱动的应急虚拟组织协作过程进行了建模分析,并提出了一种模型求解算法和算例应用.     

考虑多事故点的海上重大事故应急物资优化调度

应急物资的高效调度是整个应急系统服务效率的保障,为提升海上应急系统的救助效率,针对固定海域内多起重大事故随机发生情景下的应急物资优化调度问题展开了研究。综合考虑物资运输受需求时间窗限制、物资需求存在时变特性以及海陆物资协同调度存在耦合关系等一系列复杂约束后,为统筹优化海上应急物资调度与陆上补给应急物资调度,构建了一个两阶段应急物资动态优化调度模型。根据该模型的计算逻辑提出了一种混合启发式算法。最后通过仿真案例对模型与算法的有效性进行了验证,结果表明该研究方法能在海上重大事故应急物资调度过程中提供可靠的决策支持。     

灾害链中多资源应急调度模型与算法

灾害事故的应急资源调度是减少生命财产损失的有效手段.针对灾害链中多资源应急调度问题, 建立了多资源多受灾点应急调度模型,设计了基于图论中网络优化和线性规划优化思想的启发式算法,并分析了算法复杂性.该算法根据应急资源在原生灾害和次生灾害中的需求对资源进行分类,对灾害链中都需要的公共应急资源, 通过对模型线性松弛解的修正,降低问题的复杂性, 减少算法的计算时间;而对原生或次生灾害中需要的应急资源, 运用领域搜索方法寻找出救点,得到满意的资源调度方案. 最后通过算例验证了算法的有效性和可行性,表明算法适合较大规模的计算, 并能满足应用中的实时性要求.     

基于RHP-IVFSA的多智能体编组#br# 任务分配动态优化

智能体编组协同作战中任务分配的动态优化问题，提出一种基于滚动时域策略的多编组任务分配动态优化方法。以任务执行效率为目标函数，建立了满足个体任务时窗和编组资源损耗约束的问题模型。给出与突发事件特征对应的预测窗口、滚动窗口和滚动驱动机制。设计了一种改进快速模拟退火对优化子问题予以求解，给出解方案表达、邻域解生成、冲突消解等步骤，采用高温随机贪婪搜索、回火技术、禁忌设计和精英保留策略，避免算法陷入局部最优，提高算法的计算效率。案例的仿真计算表明，所建模型和求解方法可以对多编组任务分配计划进行在线优化，并使任务的执行效率始终维持较高水平。     

Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems.Although many scheduling algorithms have been proposed,emergency tasks,characterized as importance and urgency(e.g.,observation tasks orienting to the earthquake area and military conflict area),have not been taken into account yet.Therefore,it is crucial to investigate the satellite integrated scheduling methods,which focus on meeting the requirements of emergency tasks while maximizing the profit of common tasks.Firstly,a pretreatment approach is proposed,which eliminates conflicts among emergency tasks and allocates all tasks with a potential time-window to related orbits of satellites.Secondly,a mathematical model and an acyclic directed graph model are constructed.Thirdly,a hybrid ant colony optimization method mixed with iteration local search(ACO-ILS) is established to solve the problem.Moreover,to guarantee all solutions satisfying the emergency task requirement constraints,a constraint repair method is presented.Extensive experimental simulations show that the proposed integrated scheduling method is superior to two-phased scheduling methods,the performance of ACO-ILS is greatly improved in both evolution speed and solution quality by iteration local search,and ACO-ILS outperforms both genetic algorithm and simulated annealing algorithm.     

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

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

虚拟化云中随机任务与资源调度方法

任务和资源调度方法是云系统的关键技术之一。但是,现有的研究往往忽略实时任务的高动态性和任务执行时间的随机性,使得调度方案的实际性能与期望性能相差甚远。针对以上问题,本文设计一个随机性感知的调度框架;提出一个启发式调度算法集成前摄性和反应式策略(proactive and reactive strategy, PRS)来对任务进行调度,以提高云系统保障实时任务时效性的能力;并提出3个计算资源伸缩策略来动态调整计算资源,以减少能量消耗。最后,通过实验将算法PRS的性能与其他4个算法进行比较。实验结果表明,在任务完成率和能耗方面,算法PRS的性能比已有算法提高13.85%和17.23%。     

基于改进DE算法的敏捷成像卫星前摄式调度

针对卫星资源失效或应急任务加入对敏捷成像卫星前摄式调度的影响,构建了鲁棒模型,提出了一种改进差分进化(differential evolution,DE)算法。首先,考虑卫星资源失效概率、任务执行主从窗口构建了期望收益和松弛时间指标,将这两个指标作为优化目标构建了前摄式调度鲁棒模型;然后,针对该模型的多目标优化特性,在传统DE算法的基础上,重新设计了变异、交叉和选择算子,增加了外部存档更新策略,优化了Pareto解集评价指标,提出一种多目标离散差分进化(multi-objective discrete differential evolution,MDDE)算法,并给出了算法的实现步骤;最后,仿真结果表明,与NSGA-Ⅱ算法相比,MDDE在Pareto解集评价指标上提高了10.42%左右,在求解时间上降低了9.72%左右,为敏捷成像卫星前摄式调度提供了一定的方法支撑。     

一种基于动态关键路径的递归并行调度算法

并行任务在多处理机系统上的有效调度是获得系统高性能的关键所在.对BNP(Bounded Number Processors)调度问题,提出了一种新的基于动态关键路径的递归调度算法,对调度节点进行递归选择,并结合调度节点的后继任务为它选择了最佳时间槽.该算法克服了已有调度算法不能保证对动态关键任务进行最早调度这一缺点,优于现有BNP调度算法.     

考虑卫星指令上注的两阶段应急任务规划

多星对地观测应急任务具有突发性和高时效性,不同于常规任务的任务规划,应急任务规划需快速响应任务需求。考虑多星应急任务规划指令上注和数据下传这两个制约应急任务规划的关键因素,设计了基于固定周期的决策统筹规划和基于测控站的局部调整规划相结合的任务规划调度策略。在满足应急任务尽早下传的条件下,提出一种两阶段算法来解决不确定到达的应急任务的动态规划问题。最后通过实验验证了所提算法解决应急任务规划的有效性。     

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

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

可重构计算平台上软硬件任务划分与调度算法

软硬件任务划分和任务调度是保证任务集合在可重构计算平台上高效运行的重要技术。传统上软硬件任务划分与任务调度独立进行,划分方案和调度方案不一定匹配,加速效果难以保证。提出了一种将软硬件任务划分与任务调度相结合的算法。该算法综合考虑了任务的执行时间、任务间的通信开销、任务间的依赖关系以及计算资源间的并发关系,可以同时获得给定任务集的软硬件任务划分方案和任务调度方案,加速效果良好。算法开销与传统的任务调度算法相当,时间复杂度为O(V²log₂V+PVlog₂V)实验结果表明了该算法的可行性和有效性。     

战时装备维修任务调度的两种新算法

针对基于最大保障时间的战时维修任务调度问题,建立了以维修效益最大为目标的调度模型,并给出了两种模型求解算法。算法1以最大保障时间和维修效益作为维修任务的优先级设计参数,充分考虑了维修任务的紧迫性与价值;算法2进一步考虑维修小组的可维修装备数量,使得各小组的维修负载更加均衡。利用该方法,在满足作战单元最大保障时间的前提下,可使得装备维修效益最大,有效地解决了战时维修任务的调度问题。