Makespan-Minimizing Heterogeneous Task Allocation under Temporal Constraints
Open Access
- 14 December 2023
- Vol. 10 (12) , 1032
Abstract
Task allocation is an essential element for determining the capability of multi-UAV systems to perform various tasks. This paper presents a procedure called a “rebalancing algorithm” for generating task-performing routes in heterogeneous multi-UAV systems. The algorithm adopts a greedy-based heuristic approach to find solutions efficiently in dynamically changing environments. A novel variable named “loitering” is introduced to satisfy temporal constraints, resulting in improved performance compared to heuristic algorithms: a sequential greedy algorithm, a genetic algorithm, and simulated annealing. The rebalancing algorithm is divided into two phases to minimize the makespan, i.e., the initial allocation and reallocation phases. Simulation results demonstrate the proposed algorithm’s effectiveness in highly constrained conditions and its suitability for heterogeneous systems. Additionally, the results show a reduction in calculation time and improved performance compared to the heuristic algorithms.Keywords
Funding Information
- Korea Research Institute for Defense Technology (KRIT) (KRIT-CT-21-009, Development of Realtime Automatic Mission Execution and Correction Technology based on Battlefield Information, 2021)
This publication has 29 references indexed in Scilit:
- An ant colony optimization heuristic for constrained task allocation problemJournal of Computational Science, 2015
- Task Allocation for Spatially and Temporally Distributed Tasks2013
- A Centralized Multi-Robot Task Allocation for Industrial Plant Inspection by Using A* and Genetic Algorithms2012
- Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed systemJournal of Parallel and Distributed Computing, 2010
- Multiple UAV Task Allocation Using Particle Swarm Optimization2008
- Task allocation for maximizing reliability of distributed systems: A simulated annealing approachJournal of Parallel and Distributed Computing, 2006
- An agent‐based intelligent environmental monitoring systemManagement of Environmental Quality: An International Journal, 2004
- Genetic Algorithm for Task Allocation in UAV Cooperative Control2003
- Applicability of simulated annealing methods to real-time scheduling and jitter control2002
- Methods for task allocation via agent coalition formationArtificial Intelligence, 1998