航天测控网调度的混合构造启发式算法

Hybrid constructive heuristics of space measurement and control network scheduling problem

针对航天测控网调度问题,提出一种基于混合启发式的解构造算法。与其他构造启发式算法不同的是,本启发式算法充分利用了我国航天测控网调度需求的特点,包括优先级、任务之间时间间隔要求和一个需求包括多个相同任务要求等,综合考虑了任务局部和需求全局,融合最大可用窗口价值规则和最早可用窗口集规则。其优势在于通过动态选择构造启发式规则来提高求解质量。最后,通过仿真实验分析比较,该算法可以在不明显增加计算时间的基础上得到更高的初始解质量。

For the space measurement and control network scheduling problem,a hybrid constructive heu-ristics is proposed.Different from existing constructive heuristics,this heuristics takes advantage of characteris-tics of space measurement and control network scheduling requirements,including priorities,temporal intervals and multiple same tasks in one requirement.Considering both local tasks and the complete requirement,it in-tegrates the maximum valued available task window rule with the first available task window set rule.Its advan-tage is to improve the solution quality by means of dynamic choice of the two rules.Finally,through simulation cases and computational results analysis,it is found that this hybrid constructive heuristics can improve the solu-tion quality and increase less computation cost.