Heuristic dynamic adjust of task scheduling for earth observing satellite

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (30): 241-245.

• 工程与应用 • Previous Articles Next Articles

Heuristic dynamic adjust of task scheduling for earth observing satellite

ZHANG Lining1，HUANG Xiaojun1，QIU Dishan1，LI Haoping2

1.College of Information System and Management，National University of Defense Technology，Changsha 410073，China
2.Sub-post Box #9，Post Box #947，Haidian District，Beijing 100191，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-10-21 Published:2011-10-21

对地观测卫星任务规划的启发式动态调整算法

张利宁1，黄小军1，邱涤珊1，李皓平2

1.国防科学技术大学信息系统与管理学院，长沙 410073
2.北京市海淀区947信箱9分箱，北京 100191

Abstract

Abstract: The dynamic adjust problem of task scheduling for multi-earth observing satellite is analyzed，in cases of single resource fail and multi-prior tasks’ dynamic insertion.The optimizing objective is to maximize the sum of all scheduled tasks.The heuristic dynamic adjust algorithm has been proposed based on task swapping，including five heuristic strategies to choosing swapped task：maximum flexibility，minimum conflict set，minimum contention，interval prune and task prune.Two critical elements that impact efficiency of the algorithm have been analyzed also.Three indices，including re-scheduling ratio，change ratio of sum weight and total running time are deployed to check the result of this algorithm;the feasibility and effectiveness have been tested through simulation，and promised result is fulfilled.

Key words: earth-observing satellite, task scheduling, resource fail, dynamic task insertion, heuristic algorithm

摘要： 针对对地观测卫星任务规划，分析了单个资源失效与多个高优先级任务动态插入情况下已有任务规划方案的动态调整问题。以最大化规划方案任务权值总和为优化目标，提出了基于任务替换的启发式动态调整算法，包括选择替换任务的五种启发式策略：最大灵活度、最小冲突集、最小争议部分、区间剪枝以及任务剪枝策略。分析了影响动态调整算法运行效率的两个关键因素：冲突任务集与动态搜索深度。采用任务重规划率、规划权值变化率与算法运行时间三项指标考察算法效果，通过仿真实验验证了算法的可行性和有效性。

关键词: 对地观测卫星, 任务规划, 资源失效, 动态任务插入, 启发式算法

ZHANG Lining1，HUANG Xiaojun1，QIU Dishan1，LI Haoping2. Heuristic dynamic adjust of task scheduling for earth observing satellite[J]. Computer Engineering and Applications, 2011, 47(30): 241-245.

张利宁1，黄小军1，邱涤珊1，李皓平2. 对地观测卫星任务规划的启发式动态调整算法[J]. 计算机工程与应用, 2011, 47(30): 241-245.

[1]	ZHANG Chi, WANG Yuxin, FENG Zhen, GUO He. Energy-Efficient Task Scheduling Algorithm in Two-Layer Virtualized Cloud Architecture [J]. Computer Engineering and Applications, 2021, 57(3): 103-111.
[2]	TIAN Zhuojing, HUANG Zhenchun, ZHANG Yinong. Review of Task Scheduling Methods in Cloud Computing Environment [J]. Computer Engineering and Applications, 2021, 57(2): 1-11.
[3]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[4]	XIANG Min, DAI Keyu, ZHOU En, LIU Yu, LEI Rujie. Scheduling Strategy for IoT Terminals Considering Task Relevance [J]. Computer Engineering and Applications, 2020, 56(23): 95-102.
[5]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[6]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[7]	YU Qiaoyu，WU Yaohua，WANG Yanyan. Tasks Scheduling Optimization of Tier-to-Tier Shuttle-Based Storage and Retrieval System with Double Lifts [J]. Computer Engineering and Applications, 2020, 56(20): 270-278.
[8]	YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79.
[9]	HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171.
[10]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[11]	SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2. Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem [J]. Computer Engineering and Applications, 2019, 55(5): 44-50.
[12]	WU Bo, XU Daoqiang, ZOU Yunfeng, WANG Tiantian, LI Xin. Stage-Aware Geo-Distributed Data Analytics Job Insurance Mechanism [J]. Computer Engineering and Applications, 2019, 55(23): 78-85.
[13]	ZHU Yongchao, ZHOU Chuan, GUO Jian, WU Yifei, CUI Yuwei. New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems [J]. Computer Engineering and Applications, 2019, 55(21): 93-98.
[14]	TANG Linyu, JIANG Jiafu, GU Ke. Computing Resource Allocation Scheme Based on Fog Computing [J]. Computer Engineering and Applications, 2019, 55(19): 96-104.
[15]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.

Heuristic dynamic adjust of task scheduling for earth observing satellite

对地观测卫星任务规划的启发式动态调整算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics