Lin等单星每日成像调度：启发式插入与冲突消解模型

文献与适用边界

对应文献：Lin, W.-C.; Liao, D.-Y.; Liu, C.-Y.; Lee, Y.-Y. Daily Imaging Scheduling of an Earth Observation Satellite. IEEE Transactions on Systems, Man, and Cybernetics - Part A, 2005.

该文面向单颗对地观测卫星的日成像计划。其重点是工程化日计划生成，不是光学/SAR双载荷，但它适合说明单平台在有限时间窗内如何用启发式方法快速生成可执行任务序列。

算法思路

每日成像调度通常面对大量用户请求。精确求解成本高，因此工程上常采用“排序-插入-冲突消解”的启发式流程：先按优先级、截止时间或收益密度排序任务，再逐个尝试插入已有计划；若插入产生冲突，则比较收益并删除或移动低价值任务。

同平台光学/SAR调度中，该思路可用于快速生成初始计划：先安排高优先级应急任务，再把光学/SAR候选窗口按收益密度插入，并用资源约束检查器消解冲突。

变量定义

任务 $i$ 的优先级为 $p_i$，成像持续时间为 $d_i$，可执行窗口为 $[a_i,b_i]$，计划开始时间为 $s_i$。若任务 $i$ 被接受：

$$x_i=1,\quad a_i\le s_i,\quad s_i+d_i\le b_i$$

若任务 $i$ 位于任务 $j$ 前面，则：

$$s_j\ge s_i+d_i+\tau_{ij}$$

其中 $\tau_{ij}$ 是姿态或载荷切换时间。

收益密度推导

启发式排序常用任务收益密度：

$$\eta_i=\frac{p_i}{d_i+\bar{\tau}_i}$$

其中 $\bar{\tau}_i$ 表示插入任务 $i$ 可能引起的平均机动或切换时间。对光学/SAR同平台，可扩展为：

$$\eta_{im}=\frac{p_i q_{im}}{d_{im}+\bar{\tau}_{im}+ \lambda_E e_{im}+\lambda_D v_{im}}$$

其中 $q_{im}$ 是载荷 $m$ 的预计成像质量，$e_{im}$ 是能耗，$v_{im}$ 是数据量。SAR任务通常 $e_{i,SAR}$ 和 $v_{i,SAR}$ 较大，因此若仅收益相同，其收益密度可能低于光学；但在云量高或夜间时，光学质量 $q_{i,OPT}$ 下降，SAR会更有优势。

约束推导

任务插入时需要检查三类约束：

时间窗约束：

$$a_i\le s_i,\quad s_i+d_i\le b_i$$

相邻任务可转移约束：

$$s_i \ge s_{pre}+d_{pre}+\tau_{pre,i}$$ $$s_{next}\ge s_i+d_i+\tau_{i,next}$$

资源约束可递推：

$$E(t+1)=E(t)+E^{in}(t)-\sum_i e_i x_i(t)\ge E^{min}$$ $$S(t+1)=S(t)+\sum_i v_i x_i(t)-D(t)\le S^{max}$$

算法流程

1. 计算每个候选任务或“任务-载荷”组合的收益密度。
2. 按收益密度、截止时间或优先级排序。
3. 逐个尝试插入当前计划中所有可行位置。
4. 对每个插入位置检查时间窗、姿态转移、载荷互斥、能量、存储和热控。
5. 若没有可行位置，尝试删除低收益冲突任务并重新插入。
6. 输出日计划，并在执行中根据云量或突发任务滚动修正。

对同平台光学/SAR的意义

该启发式不保证全局最优，但很适合工程系统生成初始可行解。对光学/SAR同平台，可把候选任务扩展为 ((i,OPT))、((i,SAR))、((i,OPT+SAR))，用收益密度统一比较。其局限是规则依赖较强，难以处理复杂多目标权衡；因此通常需要与局部搜索或滚动重规划结合。

论文截图（算法流程、步骤与效果）

截图来自对应论文 PDF 页面，并已通过 PicGo 上传。用于快速定位原文中的算法流程、关键步骤或实验效果；若截图为相关替代文献，已在说明中标注。

截图 1：算法/模型页：每日成像调度的启发式求解与约束处理

来源：R01_Daily Imaging Scheduling of an Earth Observation Satellite.pdf，PDF 第 5 页。

截图 2：实验/效果页：任务数据、调度结果与对比表

来源：R01_Daily Imaging Scheduling of an Earth Observation Satellite.pdf，PDF 第 8 页。