A Novel Memetic Algorithm for Energy-Efficient Distributed Heterogeneous Flexible Job Shop Scheduling: Case Studies in AAVs Delivery

Autonomous aerial vehicles (AAVs) are gaining more and more attention due to their low cost and high efficiency in delivery problems, and they can be converted into job shop scheduling problems (JSPs). In this article, a AAVs delivery problem is modeled as an energy-efficient distributed heterogeneous flexible JSP (EEDHFJSP), an extension of the flexible JSP, with the objectives of minimizing makespan and total energy consumption (TEC). We propose a memetic algorithm with a novel neighborhood structure and a heuristic selection strategy (NSHSM). A new neighborhood structure is designed to consider energy efficiency, combined with a classic neighborhood structure for flexible job shop scheduling to perform local search. Additionally, a heuristic selection operator strategy is developed based on the characteristics of these two neighborhood structures. NSHSM is compared with five state-of-the-art multiobjective optimization algorithms, including MOEA/D, NSGA-II, TS-NSGA-II, IMANS, and DQCE. Experimental results demonstrate that NSHSM outperforms the compared algorithms in terms of both makespan and TEC, highlighting its effectiveness in solving the EEDHFJSP and AAVs delivery problem.