Computer Science ›› 2019, Vol. 46 ›› Issue (10): 90-96.doi: 10.11896/jsjkx.180901806

• Network & Communication • Previous Articles     Next Articles

Satellite Reactive Scheduling Based on Heuristic Algorithm

ZHANG Ming1, WEI Bo2, WANG Jin-dong1   

  1. (PLA Information Engineering University,Zhengzhou 450001,China)1
    (Beijing Institute of Remote Sensing Information,Beijing 100101,China)2
  • Received:2018-09-27 Revised:2018-12-06 Online:2019-10-15 Published:2019-10-21

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
[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)
[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)
[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)
[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)
[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] 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.
Full text



No Suggested Reading articles found!