基于启发式算法的卫星反应式调度

doi:10.11896/jsjkx.180901806

Abstract

Abstract: For the sudden events such as earthquakes and fires,it is necessary to dynamically adjust the satellite dispatching plan.Considering the dynamic uncertainty factors such as satellite resource failure and joining emergency task,combining task constraints,time constraints,satellite energy and storage constraints,this paper designed an event-driven strategy based on trigger rules,constructed a multi-objective optimazation model regarding maximized scheduling gain and minimum disturbance measure as objective function,and then proposed a heuristic algorithm considering task merging,insertion,shifting and replacement.The simulation results show that the event-driven strategy based on trigger rules can balance the number of triggers,task completion rate and response time,and it is an effective reactive driving strategy.Compared with other three algorithms,the MISR-HA algorithm improves the scheduling gain by an average of 14.78%,reduces the disturbance measurement by an average of 41.91%,and reduces the running time by an average of 14.63%,thus proving the effectiveness of the algorithm.

Key words: Constraint condition, Dispatch income, Disturbance measure, Heuristic method, Trigger rule

CLC Number:

TP79

ZHANG Ming, WEI Bo, WANG Jin-dong. Satellite Reactive Scheduling Based on Heuristic Algorithm[J].Computer Science, 2019, 46(10): 90-96.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Satellite Reactive Scheduling Based on Heuristic Algorithm

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 5

Metrics

Comments

Recommended 0

[1]	TANG Wen-jun, LIU Yue, CHEN Rong. User Allocation Approach in Dynamic Mobile Edge Computing [J]. Computer Science, 2021, 48(1): 58-64.
[2]	XU Xiang-yu and LIU Jian-ming. Collaborative Filtering Recommendation Algorithm Based on Multi-level Item Similarity [J]. Computer Science, 2016, 43(10): 262-265.
[3]	LIU Bin and ZHOU Li-juan. Heuristic Method for Identifying P2P Application Based on IP Address Entropy [J]. Computer Science, 2014, 41(Z6): 300-302.
[4]	LIAO Tao, LIU Zong-tian, SUN Rong. Research and Implementation of Web Table Positioning Technology [J]. Computer Science, 2009, 36(9): 227-230.
[5]	. [J]. Computer Science, 2006, 33(1): 31-34.