Journal
IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS
Volume 22, Issue 9, Pages 5926-5938Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TITS.2020.3042670
Keywords
Task analysis; Scheduling; Processor scheduling; Resource management; Heuristic algorithms; Job shop scheduling; Unmanned aerial vehicles; Task scheduling; multi-UAV; divide and conquer framework; two-phase optimization method; SATL-VND
Categories
Funding
- National Natural Science Foundation of China [62073341, 61773390]
- Natural Science Fund for Distinguished Young Scholars of Hunan Province [2019JJ20026]
- Natural Science Foundation of Hunan Province [2020JJ4748]
Ask authors/readers for more resources
This paper presents a divide and conquer framework for multi-UAV task scheduling, which partitions the original problem into multiple sub-problems and iteratively optimizes the scheduling scheme through algorithms to generate efficient task schedules.
Task scheduling of multiple UAVs has become a highly active area of research in recent years. Previous research has generally solved the problem in a whole manner, which makes it hard to efficiently generate high-quality task scheduling schemes due to prohibitive computational complexity. By contrast, the paper constructs a novel divide and conquer framework for multi-UAV task scheduling (DCF), which partitions the original multi-UAV scheduling problem into multiple scheduling sub-problems for all the UAVs. To be specific, DCF includes two phases: one is the task allocation phase which produces multiple scheduling sub-problems and the other is the single UAV scheduling phase which generates the scheduling scheme with sequential tasks for each single UAV considering constraints involving UAV capabilities and task demands. Two phases are iteratively performed until the predefined stopping criteria are met. In the task allocation phase, we propose a tabu-list-based simulated annealing (SATL) algorithm to realize task allocation among multiple UAVs. After obtaining the task allocation scheme, a satisfactory scheduling scheme of each single UAV is generated by variable neighborhood descent (VND) algorithm. Extensive experiments and comparative studies are conducted, demonstrating the efficiency of DCF and the proposed SATL-VND algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available