| 主权项 |
一种基于动态规划的前瞻启发式卫星任务规划算法，其特征在于，对于某一次前瞻操作，假设当前待规划的任务是t<sub>i</sub>，第i个任务的规划时刻为<img file="FDA0001079980400000011.GIF" wi="63" he="60" />求解目标是以优先级之和为评价指标从任务集{t<sub>i</sub>,…,t<sub>i+m‑1</sub>,…,t<sub>i+K‑1</sub>}中找出一个最优任务规划方案，然后判断t<sub>i</sub>是否在此方案中，并依次判断它的取舍问题；首先用M(m,s)表示以<img file="FDA0001079980400000012.GIF" wi="160" he="55" />为开始规划时刻、任务集{t<sub>i+m‑1</sub>,…,t<sub>i+K‑1</sub>}中最优规划方案的优先级之和，其中1≤m≤K、<img file="FDA0001079980400000013.GIF" wi="382" he="59" />都是正整数，e<sub>i+K‑1</sub>为第i+K‑1个任务的结束时间，从而将求解目标转化为求M(1,1)及其对应的规划方案，具体步骤如下：Step 1：设置循环变量i＝1，代表当前待处理的任务是t<sub>i</sub>；已安排任务优先级之和为p＝0；已规划序列<img file="FDA0001079980400000014.GIF" wi="141" he="42" />第一个任务的规划时刻为<img file="FDA0001079980400000015.GIF" wi="128" he="59" />Step 2：对于当前任务t<sub>i</sub>，为判断它是否应当安排，按如下步骤找出其对应的前瞻子任务集合中的最优规划序列T<sub>i</sub>：Step2.1：按照公式<img file="FDA0001079980400000016.GIF" wi="779" he="153" />和<img file="FDA0001079980400000017.GIF" wi="622" he="57" />计算矩阵M的边界值，其中，Μ(1,1)是最优前瞻任务规划方案对应的任务优先级之和，s<sub>i+K‑1</sub>为第i+K‑1个任务的开始时间，p<sub>i+K‑1</sub>为第i+K‑1个任务的优先级；Step2.2：按照公式<img file="FDA0001079980400000018.GIF" wi="1614" he="157" />计算矩阵M的所有其它元素值，每个单元只计算一次，其中，e<sub>i+m‑1</sub>为第i+m‑1个任务的结束时间，s<sub>i+m‑1</sub>为第i+m‑1个任务的开始时间，p<sub>i+m‑1</sub>为第i+m‑1个任务的优先级；Step 2.3：根据矩阵M中的信息，用回退法求M(1,1)对应的规划方案T<sub>i</sub>；Step 3：如果t<sub>i</sub>包含在规划序列T<sub>i</sub>中，则T＝T∪{t<sub>i</sub>}，p＝p+p<sub>i</sub>，s＝max(s,e<sub>i</sub>)，其中，p<sub>i</sub>为第i个任务的优先级，e<sub>i</sub>为第i个任务的结束时间；Step 4：如果i＜N<sub>t</sub>，则i＝i+1转向Step 2；否则算法结束，T即为规划结果，其中N<sub>t</sub>表示总任务数。 |
