Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites

Maocai Wang, Guangming Dai, Massimiliano Vasile

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

Imaging satellite scheduling is an NP-hard problem with many complex constraints. This paper researches the scheduling problem for dynamic tasks oriented to some emergency cases. After the dynamic properties of satellite scheduling were analyzed, the optimization model is proposed in this paper. Based on the model, two heuristic algorithms are proposed to solve the problem. The first heuristic algorithm arranges new tasks by inserting or deleting them, then inserting them repeatedly according to the priority from low to high, which is named IDI algorithm. The second one called ISDR adopts four steps: insert directly, insert by shifting, insert by deleting, and reinsert the tasks deleted. Moreover, two heuristic factors, congestion degree of a time window and the overlapping degree of a task, are employed to improve the algorithm’s performance. Finally, a case is given to test the algorithms. The results show that the IDI algorithm is better than ISDR from the running time point of view while ISDR algorithm with heuristic factors is more effective with regard to algorithm performance. Moreover, the results also show that our method has good performance for the larger size of the dynamic tasks in comparison with the other two methods.
LanguageEnglish
Article number234928
Number of pages11
JournalMathematical Problems in Engineering
Volume2014
DOIs
Publication statusPublished - 17 Jul 2014

Fingerprint

Heuristic algorithms
Scheduling algorithms
Scheduling Algorithm
Heuristic algorithm
Imaging
Satellites
Imaging techniques
Scheduling
Heuristics
Time Windows
Dynamic Properties
NP-hard Problems
Optimization Model
Emergency
Congestion
Overlapping
Scheduling Problem
Computational complexity

Keywords

  • satellite scheduling
  • heuristic algorithms
  • dynamic tasks
  • earth observation satellites

Cite this

@article{44e0b4059c084960bee42fc1197ca921,
title = "Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites",
abstract = "Imaging satellite scheduling is an NP-hard problem with many complex constraints. This paper researches the scheduling problem for dynamic tasks oriented to some emergency cases. After the dynamic properties of satellite scheduling were analyzed, the optimization model is proposed in this paper. Based on the model, two heuristic algorithms are proposed to solve the problem. The first heuristic algorithm arranges new tasks by inserting or deleting them, then inserting them repeatedly according to the priority from low to high, which is named IDI algorithm. The second one called ISDR adopts four steps: insert directly, insert by shifting, insert by deleting, and reinsert the tasks deleted. Moreover, two heuristic factors, congestion degree of a time window and the overlapping degree of a task, are employed to improve the algorithm’s performance. Finally, a case is given to test the algorithms. The results show that the IDI algorithm is better than ISDR from the running time point of view while ISDR algorithm with heuristic factors is more effective with regard to algorithm performance. Moreover, the results also show that our method has good performance for the larger size of the dynamic tasks in comparison with the other two methods.",
keywords = "satellite scheduling, heuristic algorithms, dynamic tasks, earth observation satellites",
author = "Maocai Wang and Guangming Dai and Massimiliano Vasile",
note = "Date of Acceptance: 13/06/2014",
year = "2014",
month = "7",
day = "17",
doi = "10.1155/2014/234928",
language = "English",
volume = "2014",
journal = "Mathematical Problems in Engineering",
issn = "1024-123X",

}

Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites. / Wang, Maocai; Dai, Guangming; Vasile, Massimiliano.

In: Mathematical Problems in Engineering, Vol. 2014, 234928, 17.07.2014.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites

AU - Wang, Maocai

AU - Dai, Guangming

AU - Vasile, Massimiliano

N1 - Date of Acceptance: 13/06/2014

PY - 2014/7/17

Y1 - 2014/7/17

N2 - Imaging satellite scheduling is an NP-hard problem with many complex constraints. This paper researches the scheduling problem for dynamic tasks oriented to some emergency cases. After the dynamic properties of satellite scheduling were analyzed, the optimization model is proposed in this paper. Based on the model, two heuristic algorithms are proposed to solve the problem. The first heuristic algorithm arranges new tasks by inserting or deleting them, then inserting them repeatedly according to the priority from low to high, which is named IDI algorithm. The second one called ISDR adopts four steps: insert directly, insert by shifting, insert by deleting, and reinsert the tasks deleted. Moreover, two heuristic factors, congestion degree of a time window and the overlapping degree of a task, are employed to improve the algorithm’s performance. Finally, a case is given to test the algorithms. The results show that the IDI algorithm is better than ISDR from the running time point of view while ISDR algorithm with heuristic factors is more effective with regard to algorithm performance. Moreover, the results also show that our method has good performance for the larger size of the dynamic tasks in comparison with the other two methods.

AB - Imaging satellite scheduling is an NP-hard problem with many complex constraints. This paper researches the scheduling problem for dynamic tasks oriented to some emergency cases. After the dynamic properties of satellite scheduling were analyzed, the optimization model is proposed in this paper. Based on the model, two heuristic algorithms are proposed to solve the problem. The first heuristic algorithm arranges new tasks by inserting or deleting them, then inserting them repeatedly according to the priority from low to high, which is named IDI algorithm. The second one called ISDR adopts four steps: insert directly, insert by shifting, insert by deleting, and reinsert the tasks deleted. Moreover, two heuristic factors, congestion degree of a time window and the overlapping degree of a task, are employed to improve the algorithm’s performance. Finally, a case is given to test the algorithms. The results show that the IDI algorithm is better than ISDR from the running time point of view while ISDR algorithm with heuristic factors is more effective with regard to algorithm performance. Moreover, the results also show that our method has good performance for the larger size of the dynamic tasks in comparison with the other two methods.

KW - satellite scheduling

KW - heuristic algorithms

KW - dynamic tasks

KW - earth observation satellites

UR - http://www.hindawi.com/journals/mpe/

U2 - 10.1155/2014/234928

DO - 10.1155/2014/234928

M3 - Article

VL - 2014

JO - Mathematical Problems in Engineering

T2 - Mathematical Problems in Engineering

JF - Mathematical Problems in Engineering

SN - 1024-123X

M1 - 234928

ER -