Design of task priority model and algorithm for imaging observation problem

doi:10.23919/JSEE.2020.000010

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (2): 321-334.doi: 10.23919/JSEE.2020.000010

• Systems Engineering • Previous Articles Next Articles

Design of task priority model and algorithm for imaging observation problem

Jian WU¹(), Fang LU²(), Jiawei ZHANG^1,^3,*(), Jiawei ZHANG⁴(), Lining XING^1,²()

¹ College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
² College of Logistics and Transportation, Central South University of Forestry and Technology, Changsha 410004, China
³ College of Information and Communication, National University of Defense Technology, Xi'an 710106, China
⁴ College of Engineering, Shanghai Polytechnic University, Shanghai 201209, China

Received:2019-03-29 Online:2020-04-30 Published:2020-04-30
Contact: Jiawei ZHANG E-mail:1551699723@qq.com;717290412@qq.com;418114952@qq.com;jhyang@sspu.edu.cn;xing2999@qq.com
About author:WU Jian was born in 1994. He received his M.S. degree from Hunan University of Technology in 2015. He is currently pursuing his Ph.D. degree with the National University of Defense Technology. His research interests include intelligent optimization and task scheduling. E-mail: 1551699723@qq.com|LU Fang was born in 1979. She is currently a professor in College of Logistics and Transportation at Central South University of Forestry and Technology. Her research interests include information system and supply chain management. E-mail: 717290412@qq.com|ZHANG Jiawei was born in 1995. He received his M.S. degree from National University of Defense Technology in 2018. His research interests include intelligent optimization and task scheduling. E-mail: 418114952@qq.com|YANG Jinghui was born in 1969. She is currently a professor in the College of Engineering at Shanghai Polytechnic University. Her research interests include information system and engineering management. E-mail: jhyang@sspu.edu.cn|XING Lining was born in 1980. He is currently a professor in National University of Defense Technology. His research interests include intelligent optimization and task scheduling. E-mail: xing2999@qq.com
Supported by:
the National Natural Science Foundation of China(61773120);the National Natural Science Foundation of China(61473301);the National Natural Science Foundation of China(71501180);the National Natural Science Foundation of China(71501179);the National Natural Science Foundation of China(61603400);This work was supported by the National Natural Science Foundation of China (61773120; 61473301; 71501180; 71501179; 61603400)

Abstract

Abstract:

In the imaging observation system, imaging task scheduling is an important topic. Most scholars study the imaging task scheduling from the perspective of static priority, and only a few from the perspective of dynamic priority. However, the priority of the imaging task is dynamic in actual engineering. To supplement the research on imaging observation, this paper proposes the task priority model, dynamic scheduling strategy and Heuristic algorithm. At first, this paper analyzes the relevant theoretical basis of imaging observation, decomposes the task priority into four parts, including target priority, imaging task priority, track, telemetry & control (TT&C) requirement priority and data transmission requirement priority, summarizes the attribute factors that affect the above four types of priority in detail, and designs the corresponding priority model. Then, this paper takes the emergency tasks scheduling problem as the background, proposes the dynamic scheduling strategy and heuristic algorithm. Finally, the task priority model, dynamic scheduling strategy and heuristic algorithm are verified by experiments.

Key words: imaging observation system, imaging task priority, task priority model, dynamic scheduling strategy, heuristic algorithm

Jian WU, Fang LU, Jiawei ZHANG, Jiawei ZHANG, Lining XING. Design of task priority model and algorithm for imaging observation problem[J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 321-334.

Figures/Tables 35

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

Table 9

Table 10

Table 11

Table 12

Table 13

Table 14

Table 15

Table 16

Table 17

Table 18

Table 19

Table 20

Table 21

Table 22

Table 23

Table 24

Table 25

Table 26

Fig 1

Fig 2

Fig 3

Table 27

Table 28

Table 29

Fig 4

Table 30

Table 31

References 26

1	SUN X, SKILLMAN D R, HOFFMAN E D, et al. Free space laser communication experiments from Earth to the Lunar Reconnaissance Orbiter in lunar orbit. Optics Express, 2013, 21 (2): 1865- 1871.
2	SEMGHOUNI S, AMANTON L, SADEG B, et al. On new scheduling policy for the improvement of firm RTDBSs performances. Data and Knowledge Engineering, 2007, 63 (2): 414- 432.
3	CHANTEM T, WANG X, LEMMON M D, et al. Period and deadline selection for schedulability in real-time systems. Proc. of the Euromicro Conference on Real-time Systems, 2008: 168-177.
4	Minimum deadline calculation for periodic real-time tasks in dynamic priority systems. IEEE Trans. on Computers, 2008, 57 (1): 96- 109.
5	JIN H, WANG H A, WANG Q, et al. An integrated design method of task priority. Journal of Software, 2003, 14 (3): 376- 382.
6	BURNS A, PRASAD D, BONDAVALLI A, et al. The meaning and role of value in scheduling flexible real-time systems. Journal of Systems Architecture, 2000, 46 (4): 305- 325.
7	BUTTAZZO G, SPURI M, SENSINI F. Value vs. deadline scheduling in overload conditions. Proc. of the IEEE Real-time Systems Symposium, 1995: 90-99.
8	ALDARMI S A, BURNS A. Dynamic value-density for scheduling real-time systems. Proc. of the Euromicro Conference on Real-time Systems, 1999: 270-277.
9	WANG J, DUAN Q, JIANG Y, et al. A new algorithm for grid independent task schedule: genetic simulated annealing. Proc. of the World Automation Congress, 2010: 165-171.
10	ZHAN S H, LIN J, ZHANG Z J, et al. List-based simulated annealing algorithm for traveling salesman problem. Computational Intelligence and Neuroscience, 2016, 2016, 1- 12.
11	SHI J, LU H, MAO K. Solving the test task scheduling problem with a genetic algorithm based on the scheme choice rule. Proc. of the International Conference on Swarm Intelligence, 2016: 19-27.
12	DING Z H, LU Z R, LIU J K. Parameters identification of chaotic systems based on artificial bee colony algorithm combined with cuckoo search strategy. Science China Technological Sciences, 2018, 61 (3): 417- 426. doi: 10.1007/s11431-016-9026-4
13	MURRIETAMENDOZA A, BOTEZ R M, BUNEL A. Four-dimensional aircraft en route optimization algorithm using the artificial bee colony. Journal of Aerospace Information Systems, 2018, 15 (6): 307- 334.
14	WITKOWSKI T, ANTCZAK P, ANTCZAK A. Multi-objective decision making and search space for the evaluation of production process scheduling. Bulletin of the Polish Academy of Sciences: Technical Sciences, 2009, 57 (3): 195- 208. doi: 10.2478/v10175-010-0121-4
15	XU Y, LI K, HU J, et al. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 2014, 270 (20): 255- 287. doi: 10.1016/j.ins.2014.02.122
16	KOODZIEJ J, KHAN S U. Multi-level hierarchic genetic-based scheduling of independent jobs in dynamic heterogeneous grid environment. Information Sciences, 2012, 214, 1- 19. doi: 10.1016/j.ins.2012.05.016
17	FERRANDI F, LANZI P L, PILATO C, et al. Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29 (6): 911- 924.
18	KIM H J, KANG S. Communication-aware task scheduling and voltage selection for total energy minimization in a multiprocessor system using ant colony optimization. Information Sciences, 2011, 181 (18): 3995- 4008. doi: 10.1016/j.ins.2011.04.037
19	ZHONG Y G, AI B. A modified ant colony optimization algorithm for multi-objective assembly line balancing. Soft Computing, 2017, 21 (22): 6881- 6894. doi: 10.1007/s00500-016-2240-9
20	PENDHARKAR P C. An ant colony optimization heuristic for constrained task allocation problem. Journal of Computational Science, 2015, 7, 37- 47. doi: 10.1016/j.jocs.2015.01.001
21	LI H, WANG L, LIU J. Task scheduling of computational grid based on particle swarm algorithm. Proc. of the 3rd International Joint Conference on Computational Science & Optimization, 2010: 332-336.
22	BANKS A, VINCENT J, ANYAKOHA C. A review of particle swarm optimization. Part Ⅰ: background and development. Natural Computing, 2007, 6 (4): 467- 484.
23	AFZALIRAD M, SHAFIPOUR M. Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. Journal of Intelligent Manufacturing, 2018, 29 (2): 423- 437.
24	LU J. Improved genetic algorithm-based resource scheduling strategy in cloud computing. Proc. of the International Conference on Smart City and Systems Engineering, 2016: 230-234.
25	JI B, YUAN X, YUAN Y. Orthogonal design-based NSGA-Ⅲ for the optimal lockage co-scheduling problem. IEEE Trans. on Intelligent Transportation Systems, 2017, 18 (8): 2085- 2095. doi: 10.1109/TITS.2016.2630718
26	DUAN L, LUO B, LI Q Y, et al. Research on intelligence, surveillance and reconnaissance mission planning model and method for naval fleet. Proc. of the Chinese Control & Decision Conference, 2016: 2419-2424.

Parameter	Attribute factor		Type	Display method	Example
$Tar_{1}$	Type	Area	Enumeration	Regional target, point target	Regional target
$Tar_{2}$	Type	Status	Enumeration	Moving target, stationary target	Moving target
$Tar_{3}$	Imaging	Image type	Enumeration	Visible light, radar, infrared	Visible light
$Tar_{4}$	Imaging	Minimum ground resolution	Floating point	Positive number	1
$Tar_{5}$	Airspace	Regional coverage	Floating point	Positive number	58.7
$Tar_{6}$		Geographical characters	Enumeration	Characteristic A	Characteristic A
				Characteristic B
				Characteristic C
$Tar_{7}$	Time domain	Number of observations	Integer	Natural number	1
$Tar_{8}$	Time domain	Longest observation time/min	Integer	Natural number	0

Type		Status
Type		Stationary target	Moving target
Area	Point target	1	6
Area	Regional target	6	10

Geographical characteristic	Attribute value
Characteristic A	10
Characteristic B	7
Characteristic C	5

Number of observations	Attribute value
1	1
2	2
3	4
4	6
5	7
6	9
$ {\geqslant} 7$	10

Maximum time interval	Attribute value
$ {\leqslant} 10$	10
10–20	9
20–40	8
40–60	7
60–90	5
90–120	3
${\geqslant}120$	1

Design of task priority model and algorithm for imaging observation problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 35

References 26

Related Articles 4

Recommended Articles

Metrics

Comments

Application scenario	Attribute value
Scenario 1	1
Scenario 2	3
Scenario 3	5
Scenario 4	7
Scenario 5	9

Satellite working mode	Attribute value
Constellation	5
Single star	10

Satellite's own property	Attribute value
AW satellites	10
ES satellites	7
CU satellites	3

Parameter	Factor	Type	Display method	Example
$TTC_{1}$	Target	Float	Positive number	5.67
$TTC_{2}$	Control circle	Enumeration	Departure circle, entry circle, middle circle	Departure circle
$TTC_{3}$	TTC resource	Enumeration	Fixed ground station, mobile ground station, marine survey ship, relay satellite	Relay satellite
$TTC_{4}$	Station	Enumeration	Full-featured station, multi-function station, telemetry single receiving station	Full-featured station
$TTC_{5}$	Event	Enumeration	Remote control, telemetry, measuring track, single data reception, voice	Remote control
$TTC_{6}$	Flight stage	Enumeration	Launch, incarnation, early stage, operation	Operation
$TTC_{7}$	Number of resources available	Integer	Natural number	3
$TTC_{8}$	Execution urgency	Float	Positive number	0.72

Number	Importance level	$a_{ij}$
1	Factor $x$ is as important as factor $y$	1
2	Factor $x$ is more important than factor $y$ slightly	3
3	Factor $x$ is more important than factor $y$ obviously	5
4	Factor $x$ is more important than factor $y$	7
5	Factor $x$ is more important than factor $y$ extremely	9
6	Factor $y$ is more important than factor $x$ slightly	1/3
7	Factor $y$ is more important than factor $x$ obviously	1/5
8	Factor $y$ is more important than factor $x$	1/7
9	Factor $y$ is more important than factor $x$ extremely	1/9

Type of control circle	Attribute value
Departure circle	10
Entry circle	10
Middle circle	5

Resource	Attribute value
Fixed ground station	10
Mobile ground station	7
Marine survey ship	3
Relay satellite	1

Flight stage of satellite	Attribute value
Launch	10
Incarnation	8
Early stage	6
Operation	4
Recycle	2

Number of available resources	Attribute value
1	10
2	8
3	6
4	4
5	2
$ {\geqslant} 6$	1

Way of data transmission	Attribute value
Real-time transmission	10
Store and send	5

User	Attribute value
User A	10
User B	8
User C	6
User D	4
User E	2

Order	RI
1	0.00
2	0.00
3	0.58
4	0.90
5	1.12
6	1.24
7	1.32
8	1.41
9	1.46
10	1.49

Type	Attribute value
Optical	10
Electronic	8
Radar	5

Number	Semi major axis/km	Eccentricity	Inclination/($^\circ$)	Argument of perigee/($^\circ$)\end{tabular}	Right ascension of ascending node/($^\circ$)\end{tabular}	True anomaly/($^\circ$)
Sat1	7 171.393	0	96.576	0	175.72	0.075
Sat2	7 171.393	0	96.576	0	145.72	30.075
Sat3	7 171.393	0	96.576	0	115.72	60.075
Sat4	7 171.393	0	96.576	0	85.72	90.075
Sat5	7 171.393	0	96.576	0	55.72	120.075
Sat6	7 171.393	0	96.576	0	25.72	150.075

Receiving station	Attribute value
Station 1	10
Station 2	9
Station 3	7
Station 4	5
Station 5	3
Station 6	2
No requirement	1

Parameter	${{{\rm{task}}}}_1 $	${{{\rm{task}}}}_2 $	${{{\rm{task}}}}_3 $	${{{\rm{task}}}}_4 $	${{{\rm{task}}}}_5 $
Longitude	130.25	-50.65	78.93	-56.35	-110.58
Latitude	60.25	30.17	-17.35	-54.63	63.12
Source target priority	7.3	6.7	5.1	4.9	5.8
Application scenario	Scenario 3	Scenario 5	Scenario 2	Scenario 1	Scenario 1
User	User A	User B	User A	User C	User A
Application	Application A	Application A	Application B	Application A	Application B
Satellite working mode	Single star	Single star	Single star	Single star	Single star
Type	Emergency	Normal	Emergency	Emergency	Normal
Satellite's property	AW satellites	AW satellites	AW satellites	AW satellites	AW satellites
Flight stage	Operation	Operation	Operation	Operation	Operation
Execution urgency	0.68	0.56	0.81	0.33	0.57

Parameter		Scene
Parameter		Scene_$a$	Scene_$b$	Scene_$c$	Scene_$d$	Scene_$e$	Scene_$f$
NTotal		700
ETotal		300
Total		2 400
SUM_init	SP	75	70	65	73	72	69
SUM_init	DP	76	72	73	73	72	70
NC_init	SP	5	4	7	8	5	7
NC_init	DP	5	3	7	7	4	6
EC_init	SP	70	66	58	65	67	62
EC_init	DP	71	69	66	66	68	64
CR	SP	0.007	0.005	0.010	0.011	0.007	0.010
CR	DP	0.007	0.004	0.010	0.010	0.005	0.009
ER	SP	0.23	0.22	0.19	0.21	0.22	0.20
ER	DP	0.24	0.23	0.22	0.22	0.23	0.21
SUM	SP	1 344	1 357	1 349	1 347	1 355	1 349
SUM	DP	1 346	1 360	1 370	1 361	1 363	1 351
NC	SP	258	254	252	245	248	258
NC	DP	252	251	251	254	249	252
EC	SP	1 086	1 103	1 097	1 102	1 107	1 091
EC	DP	1 094	1 109	1 119	1 107	1 114	1 099

Scene		Scene_$g$	Scene_$h$	Scene_$i$	Scene_$j$	Scene_$k$
Total		460	820	1 540	2 260	2 980
Heuristic algorithm	Velo	15	30	60	90	120
	NT	347	591	1 138	1 791	2 518
	NR	0.754	0.721	0.739	0.792	0.845
	Time	2.07	3.69	7.47	11.90	16.48

[1]	Yajie Liu, Tao Zhang, Hongtao Lei, and Bo Guo. Stochastic programming approach for earthquake disaster relief mobilization with multiple objectives [J]. Journal of Systems Engineering and Electronics, 2013, 24(4): 642-654.
[2]	Rongwei Gan1,Qingshun Guo2,Huiyou Chang1,and Yang Yi1,*. Improved ant colony optimization algorithm for the traveling salesman problems [J]. Journal of Systems Engineering and Electronics, 2010, 21(2): 329-333.
[3]	Cheng Xu & Wu Cheng. Hybrid algorithm for project scheduling with capacity constraint [J]. Journal of Systems Engineering and Electronics, 2008, 19(5): 1041-1046.
[4]	Liu Zhenyuan & Wang Hongwei. Heuristic algorithm for RCPSP with the objective of minimizing activities' cost [J]. Journal of Systems Engineering and Electronics, 2006, 17(1): 96-102.