An Asynchronous Shuffled Frog-Leaping With Feasible Jaya Algorithm for Uncertain Task Rescheduling Problem in UAV Emergency Networks

• Published in: IEEE transactions on intelligent transportation systems 2024-10, Vol.25 (10), p.13106-13121
• Main Authors: Luan, Qiuji, Cui, Hongyan, Yu, Xi, Zhang, Lifeng, Sikdar, Biplab
• Format: Article
• Language: English
• Subjects: Autonomous aerial vehicles; Dynamic scheduling; fine-grained makespan; Heuristic algorithms; Job shop scheduling; Real-time systems; Scheduling; task rescheduling; UAV emergency network; uncertain; Uncertainty
• ISSN: 1524-9050; 1558-0016
• DOI: 10.1109/TITS.2024.3424205

Unmanned aerial vehicles (UAVs) have a great potential for assigning search and rescue operations in emergency scenarios. However, emergency scenarios are complex and unknown, regarding UAVs to reschedule to effectively adapt to the changing environment, and existing literature addressing this challenge is limited. To address this open problem, we consider a task rescheduling problem with uncertainties such as task insertion, edge computing node (ECN) destruction, and parameter fluctuation in UAV-assisted emergency networks. The goal is to minimize the fine-grained makespan, defined as the ratio of makespan to ECNs idle time, that simultaneously characterizes the optimization of rescheduling efficiency and ECNs utilization. To address the problem, we propose an asynchronous shuffled frog-leaping with feasible Jaya (ASFJ) algorithm. In ASFJ, an asynchronous shuffled frog-leaping method independently evolves memeplexes, thereby avoiding forced information coverage. Two feasible local search operators promote the search capability and feasibility of the algorithm. Finally, we verify the advantages of the ASFJ in terms of makespan, effectiveness, and fine-grained makespan. ASFJ can save 3.83ms makespan and outperform 11.2% fine-grain makespan in insertion rescheduling. The effectiveness of destruction rescheduling is improved by at least 16%.