1、自主望远镜调度算法探索,李建 lijianlamost.org2011-11-12 贵阳,Outline,关于调度系统,调度系统是自主望远镜的重要部分决定“自主化的程度”观测任务安排；资源分配均衡观测任务调度过程中，最小调度单元称为作业（job）,影响望远镜调度的因素,外部因素内部因素,影响望远镜调度的因素,外因：观测时影响观测质量的客观因素天气：雨、雪、雾、风角度：纬度越高，穿过大气层的路径越小，大气层产生的散射和变形越小，观测结果最佳月相,影响望远镜调度的因素,内因：影响作业队列顺序的内部因素主要是“效率”和“政策”“效率”因素：优先处理天体目标在相同天区的观测任务，合并相似的观测任务，只
2、执行一次观测计划，以减少望远镜的回转时间“政策”因素：包括允许管理员绕过作业队列，并优先得到望远镜的观测响应,调度方法分类,四个不同的调度类型（ Thomas Granzer 2004）:1)queue scheduling 队列调度每个观测阶段为一个jobs清单，由robot顺序执行。不可预知的延迟（如聚焦时间、快速定向时间、天气因素）就会使jobs丢失观测。不能实时插入jobs，不能改写剩余的调度队列。,调度方法分类,2）Critical Path Scheduling 关键路径调度这是一个尊重所有job依赖关系的调度方式，确保最少的依赖的job先调度，多依赖的job后调度。天文观测很少有
3、这样的依赖关系，很少使用这种方法，这不是一个合适的调度方法。3）Optimal Scheduling 优化调度这种方法需要大量的计算，来建立一个合适的时间表，以创造一个最好的调度方式。但是，预先算好的调度表还是不能对不可预知的变化作出反应。,调度方法分类,4）Dispatch Scheduling 分配调度这种类型的调度器为每个作业（job）计算出一个分数（score），放在调度池（pool）中，每次选择分数最高的执行。这种方法解决了不可预知的因素所带来的影响，因为调度不是固定的。然而，由于调度的不固定，预知robot下一步要做什么是很困难的。而且需要一个能够改变优先级的评分算法（scorin
4、g algorithm）。,调度方法分类,Liverpool Telescope、STELLA、BRT项目采取了“分配调度”的方法Hubble telescope 由于有一个更好的可以预见的环境，使用了“优化调度”的方法改进的调度方式：环状队列，双队列，多种调度方式结合,分配调度程序需求,分配调度程序应满足以下要求：所有等待处理的job，必须进行每隔几分钟进行评估、定分每个job必须结合多种因素（factor）的评价、计算出唯一的一个分数因素有加权值，反应因素的重要程度。允许管理员控制每个因素的加权值软件以模块化的方式来编写，这样在新增因素、删除旧的因素时scheduler能及时响应,分配调度
5、程序需求,当robot要求job时，scheduler不能有延迟-job必须立刻准备好在调度池内，设置为immediate标志的job，必须优先考虑分配望远镜时间，不论其分数有多少scheduler应该准许手动模式加入特殊事件，系统管理员将分配job的观测时间。,需要进行评分的因素（Score Factors）,Score Factors一些被确定为影响job的总体评分的因素： job目标达到天空中最高点的时刻 job目标落入地平的时刻 job间的相对距离（是否可以和其它观测任务合并） job预先设置的优先级值 job要求的观测时间 job一直在等待观测的时间量,Score Factor的计算
6、公式,Score Factor的计算公式,Window merit(观测窗口因素值),一个计算score的示例,布尔测试,对一个job执行scheduling算法以前，可以执行一系列布尔测试，可以减少计算时间计算出目标的高度和方位角，是否满足？Job是否过了观测时间？目标是否符合相机的操作范围？是否以正常（非特殊事件）的模式工作？,分配调度流程示例,上一次观测任务完成,从request pool提取一条任务请求,通过bool测试？,N,Y,第1个评分模块,第2个评分模块,第N个评分模块,分数加权求和,完成所有请求？,选取最高分的任务执行,N,Y,Scheduler,小结,考虑到上述所有因素，调度过程是一项复杂的任务。完全考虑到所有的因素，和它们之间的冲突是不实际的；Scheduler是保证资源公平的分配一个最优化的解决方案；是各方面因素的妥协的结果。普通望远镜，由人来决策自主望远镜，由计算机“决策”,BOOTES 4RTS2 (Remote Telescope System, 2nd Version)采用遗传算法最优化选取分布式调度,一个实际的实现的例子,Thank You !,
