The earth observation satellites(EOSs)scheduling problem for emergency tasks often presents many challenges.For example,the scheduling calculation should be completed in seconds,the scheduled task rate is supposed to ...The earth observation satellites(EOSs)scheduling problem for emergency tasks often presents many challenges.For example,the scheduling calculation should be completed in seconds,the scheduled task rate is supposed to be as high as possible,the disturbance measure of the scheme should be as low as possible,which may lead to the loss of important observation opportunities and data transmission delays.Existing scheduling algorithms are not designed for these requirements.Consequently,we propose a rolling horizon strategy(RHS)based on event triggering as well as a heuristic algorithm based on direct insertion,shifting,backtracking,deletion,and reinsertion(ISBDR).In the RHS,the driven scheduling mode based on the emergency task arrival and control station time window events are designed to transform the long-term,large-scale problem into a short-term,small-scale problem,which can improve the schedulability of the original scheduling scheme and emergency response sensitivity.In the ISBDR algorithm,the shifting rule with breadth search capability and backtracking rule with depth search capability are established to realize the rapid adjustment of the original plan and improve the overall benefit of the plan and early completion of emergency tasks.Simultaneously,two heuristic factors,namely the emergency task urgency degree and task conflict degree,are constructed to improve the emergency task scheduling guidance and algorithm efficiency.Finally,we conduct extensive experiments by means of simulations to compare the algorithms based on ISBDR and direct insertion,shifting,deletion,and reinsertion(ISDR).The results demonstrate that the proposed algorithm can improve the timeliness of emergency tasks and scheduling performance,and decrease the disturbance measure of the scheme,therefore,it is more suitable for emergency task scheduling.展开更多
基金supported by the National Natural Science Foundation of China(71671059)
文摘The earth observation satellites(EOSs)scheduling problem for emergency tasks often presents many challenges.For example,the scheduling calculation should be completed in seconds,the scheduled task rate is supposed to be as high as possible,the disturbance measure of the scheme should be as low as possible,which may lead to the loss of important observation opportunities and data transmission delays.Existing scheduling algorithms are not designed for these requirements.Consequently,we propose a rolling horizon strategy(RHS)based on event triggering as well as a heuristic algorithm based on direct insertion,shifting,backtracking,deletion,and reinsertion(ISBDR).In the RHS,the driven scheduling mode based on the emergency task arrival and control station time window events are designed to transform the long-term,large-scale problem into a short-term,small-scale problem,which can improve the schedulability of the original scheduling scheme and emergency response sensitivity.In the ISBDR algorithm,the shifting rule with breadth search capability and backtracking rule with depth search capability are established to realize the rapid adjustment of the original plan and improve the overall benefit of the plan and early completion of emergency tasks.Simultaneously,two heuristic factors,namely the emergency task urgency degree and task conflict degree,are constructed to improve the emergency task scheduling guidance and algorithm efficiency.Finally,we conduct extensive experiments by means of simulations to compare the algorithms based on ISBDR and direct insertion,shifting,deletion,and reinsertion(ISDR).The results demonstrate that the proposed algorithm can improve the timeliness of emergency tasks and scheduling performance,and decrease the disturbance measure of the scheme,therefore,it is more suitable for emergency task scheduling.
