多星任务规划中的FFFS-DTMB与ADTPC-DTMB算法

FFFS-DTMB and ADTPC-DTMB Algorithmin Multi-satellites Mission Planning

多星对地观测任务规划是一类典型组合优化问题,针对该问题中常见的时间窗口冲突问题,根据同一时间窗口内的冲突任务的处理方式提出了两种有效处理此类问题的规划算法:带有冲突任务时间窗口后移的先完成先规划算法(FFFS-DTMB)以及冲突任务共存性判断算法(ADTPC-DTMB),并给出了关键步骤的算法过程与伪代码。完整的卫星任务规划过程包括了约束检查、优先级检查以及任务规划,不考虑任务间关系与优先级,主要研究处理具有时间窗口冲突的任务规划算法。文中给出的两种算法优化目标均为最大化规划任务数量。算法的主要思路是通过采用一个冲突任务替换一个已规划的任务,并将替换任务后移至下一时间窗口或在同一时间窗口内部后移。最终的评价结果显示了两种算法的有效性。

The task scheduling for multi-earth observation satellites（EOS） is a typical combinatorial optimiza tion problem. Two scheduling algorithms are proposed which can deal with time-window crash efficiently, and solve this problem according to the ways of dealing of crashing tasks： first finish first schedule with discard task moving back（FFFS-DTMB） and accommodate discard task predicting coexistence with discard task moving back（ADTPC-DTMB）. The pseudo-codes of these two algorithms are also given. A complete EOS scheduling process includes constraints checking, priority checking and task scheduling. This article focuses on task scheduling algorithm which have an exclusion relation and the same priority. The goals of these two proposed algorithms are both maximizing the number of tasks that can be scheduled. The same rationale in these two algorithms is that a discarded task can be scheduled instead of a previously selected one by moving it hack to its next time-window or later in the same time-window. The evaluation results show that the proposed algorithms will enhance considerably the number of tasks that can be scheduled.