Oversubscribed Scheduling for NASA’s Deep Space Network: A Comparison of Optimization Techniques

This paper describes a comparison of search methods applied to the same problem of scheduling activities for NASA's Deep Space Network (DSN). The DSN consists of large (34- and 70-meter) radio antennas at three sites around the world, and provides communications and navigation support for dozens of space missions. The DSN is oversubscribed -- more time is requested than can be accommodated -- and it is an ongoing challenge to efficiently schedule the available resources while also balancing the satisfaction of requests from the disparate set of users. As part of a study of state-of-the-art solution techniques for oversubscribed scheduling, a standard set of problems was defined, and solutions were attempted with several classes of algorithms developed by different teams. These included variants of Quantum Annealing (QA), Mixed-Integer Linear Programming (MILP), and Constraint Satisfaction Problem (CSP) based heuristic search (CSP-HS). The results of this comparison show that the heuristic search method CSP-HS significantly outperforms the other methods in the study in terms of solution quality and runtime performance, when objectives are to maximize the ``fairness'' of the resulting schedule (e.g. minimize starving some users at the expense of others) while simultaneously clearing all constraint violations and fitting as much as possible into the schedule. CSP-HS shows progressively better performance on more oversubscribed problems. The set of benchmark problems is made openly available for other groups to try.

本论文针对美国国家航空航天局（NASA）深空网络（Deep Space Network, DSN）的活动调度问题，对比了多种搜索方法的性能表现。深空网络（DSN）由分布于全球三个站点的34米与70米口径大型射电天线组成，可为数十项太空任务提供通信与导航支持。该网络长期面临资源过载问题：用户申请的可用时长远超网络可承载的容量，如何高效调度现有资源，同时平衡不同用户群体的请求满意度，始终是一项持续存在的挑战性课题。作为针对过载调度问题的前沿求解技术研究的一部分，研究者定义了一套标准基准问题集，并由不同团队开发的多类算法尝试求解该问题集，所涉及的算法包括量子退火（Quantum Annealing, QA）变体、混合整数线性规划（Mixed-Integer Linear Programming, MILP）以及基于约束满足问题（Constraint Satisfaction Problem, CSP）的启发式搜索算法（CSP-HS）。本次对比实验结果表明，当优化目标为最大化最终调度方案的「公平性」（例如避免以牺牲部分用户的服务权益为代价满足其他用户的需求），同时彻底消除所有约束冲突、并尽可能多地将任务纳入调度计划时，启发式搜索方法CSP-HS在求解质量与运行性能两方面均显著优于本次研究中的其他算法。此外，CSP-HS在资源过载程度更高的问题上的表现会逐步提升。该基准问题集已对外公开，可供其他科研团队复现测试。