计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 90-96.doi: 10.11896/jsjkx.180901806
张铭1, 卫波2, 王晋东1
ZHANG Ming1, WEI Bo2, WANG Jin-dong1
摘要: 面对地震、火灾等突发性事件,需要对卫星调度方案进行动态调整。文中考虑了卫星资源失效和应急任务加入等动态不确定性因素,综合任务约束、时间约束、卫星能量和存储约束条件,设计了基于触发规则的事件驱动策略,构建了以最大化调度收益和最小化扰动测度为目标函数的反应式调度多目标优化模型,提出了基于任务迫切度的选择策略、基于时间和角度的合成策略、基于冲突程度的替换策略,最后采用了一种考虑任务合并、插入、移位、替换的启发式算法。仿真结果表明,相比事件驱动和周期驱动策略,文中所设计的基于触发规则的事件驱动策略能够兼顾触发次数、任务完成率和响应时间,是一种有效的反应式驱动策略,MISR-HA(Heuristic Algorithm for Merging,Inserting,Shifting and Replcing)算法相比其他3种算法在调度收益上平均提高了14.78%,在扰动测度上平均降低了41.91%,在运行时间上平均缩短了14.63%,从而有效地证明了该算法的有效性。
中图分类号:
[1]WANG J,ZHU X,YANG L T,et al.Towards dynamic real-time scheduling for multiple earth observation satellites[J].Journal of Computer and System Sciences,2015,81(1):110-124. [2]GRASSET-BOURDEL R,VERFAILLIE G,FLIPO A.Planning and replanning for a constellation of agile Earth observing satellites[J].Proceedings of International Conference on Automated Planning and Scheduling,2011,26(2):68-86. [3]HAO H C,JIANG W,LI Y J.Dynamic Task Planning Problem Based on Multi-Agent Agile Satellite[J].Journal of National University of Defense Technology,2013,35(1):53-59.(in Chinese) 郝会成,姜维,李一军.基于Multi-Agent敏捷卫星动态任务规划问题[J].国防科技大学学报,2013,35(1):53-59. [4]WANG J M,LI J F,TAN Y J.Study on multi-star dynamic scheduling model and algorithm with new task insertion[J].Journal of System Simulation,2009,21(12):3522-3527.(in Chinese) 王军民,李菊芳,谭跃进.有新任务插入的多星动态调度模型与算法研究[J].系统仿真学报,2009,21(12):3522-3527. [5]PEMBERTON J C,GREENWALD L G.On the need for dynamic scheduling of imaging satellites.International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences,2002,34(1):165-171. [6]KRAMER L A,SMITH S F.Maximizing Flexibility:A Retraction Heuristic for Oversubscribed Sched-uling Problems[C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence.Acapulco Mexico,2003. [7]KRAMER L A,SMITH S F.Task Swapping for Schedule Improvement:A Broader Analysis[C]//Proceedings of the 14th International Conference on Automated Planning and Scheduling.Whistler,Canada,2004. [8]KRAMER L A,SMITH S F.Task Swapping:Making Space in Schedules for Space[C]//Proceedings of the 4th International Workshop on Planning and Scheduling for Space.Darmstadt.Germany,2004. [9]KRAMER L A,SMITH S F.Maximizing flexibility:A retrac-tion heuristic for oversubscribed scheduling problems//IJCAI. 2003:1218-1223. [10]FOX M,GEREVINI A,LONG D,et al.Plan Stability:Replanning versus Plan Repair[C]//Proceedings of the International Conference on Automated Planning and Scheduling.2006:212-221. [11]LI Y Q,WANG R X,XU M Q.Scheduling and Rescheduling of Imaging Satellite Based on Ant Colony Optimization[J].Journal of Computational Information Systems,2013,9(16):6503-6510. [12]LIU Y.Research on Dynamic Rescheduling Model,Algorithm and Application of Reconnaissance Satellite [D].Changsha:National University of Defense Technology,2005.(in Chinese) 刘洋.侦察卫星动态重调度模型、算法及应用研究[D].长沙:国防科技大学,2005. [13]ZHU J H,LIU J.Local Dynamic Collaborative Rescheduling Method for Agile Satellite Observation Scheme[J].Military Planning and Systems Engineering,2014,28(3):48-52.(in Chinese) 祝江汉,刘进.敏捷卫星观测方案局部动态协同重调度方法[J].军事运筹与系统工程,2014,28(3):48-52. [14]WANG J,ZHU X,QIU D,et al.Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2275-2285. [15]WANG J,ZHU X,YANG L T,et al.Towards dynamic real-time scheduling for multiple earth observation satellites[J].Journal of Computer and System Sciences,2015,81(1):110-124. [16]BILLUPS S C.Satellite Mission Scheduling with Dynamic Tasking[R].Final Report of the UCDHSC Mathematics Clinic,2005. [17]YANG H T,YANG L,ZHAO H L.Study on the mission planning model of space-based information acquisition[J].Journal of System Simulation,2009,21(21):6710-6715. [18]FRANCOIS V,ARDA Y,CRAMA Y,et al.Large neighborhood search for multi-trip vehicle routing[J].European Journal of Operational Research,2016,255(2):422-441. [19]CHURCH L K,UZSOY R.Analysis of periodic and event-driven rescheduling policies in dynamic shops[J].International Journal of Computer Integrated Manufacturing,1992,5(3):153-163. |
[1] | 张露萍, 徐飞. 具有突触规则的脉冲神经膜系统综述 Survey on Spiking Neural P Systems with Rules on Synapses 计算机科学, 2022, 49(8): 217-224. https://doi.org/10.11896/jsjkx.220300078 |
[2] | 耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051 |
[3] | 郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波. 一种面向动态部分可重构片上系统的列表式软硬件划分算法 List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip 计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198 |
[4] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
[5] | 周秋艳, 肖满生, 张龙信, 张晓丽, 杨文理. 多约束条件下生产排程智能优化技术 Intelligent Optimization Technology of Production Scheduling Under Multiple Constraints 计算机科学, 2021, 48(3): 239-245. https://doi.org/10.11896/jsjkx.200300105 |
[6] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
[7] | 唐文君, 刘岳, 陈荣. 移动边缘计算中的动态用户分配方法 User Allocation Approach in Dynamic Mobile Edge Computing 计算机科学, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079 |
[8] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
[9] | 冯炳超, 吴璟莉. 求解自行车共享系统静态再平衡问题的单亲遗传算法 Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System 计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120 |
[10] | 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078 |
[11] | 潘恒, 李景峰, 马君虎. 可抵御内部威胁的角色动态调整算法 Role Dynamic Adjustment Algorithm for Resisting Insider Threat 计算机科学, 2020, 47(5): 313-318. https://doi.org/10.11896/jsjkx.190800051 |
[12] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
[13] | 郭超, 王磊, 尹爱华. 求解一刀切式二维矩形Strip Packing问题的混合搜索算法 Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem 计算机科学, 2020, 47(11A): 119-125. https://doi.org/10.11896/jsjkx.200200016 |
[14] | 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048 |
[15] | 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501. |
|