A Multi-objective Memetic Approach for Time-dependent Agile Earth Observation Satellite Scheduling Problem

Abstract The multi-objective agile earth observation satellite scheduling problem (MO-AEOSSP) aims to schedule tasks from a set of candidate requests, optimizing multiple criteria simultaneously. In this study, a specific bi-AEOSSP under the multi-orbit scenario is formed by considering the failure rate and the load balance degree as the two objectives to be optimized as well as the time-dependent transition time. Owing to the time-dependent transition time, bidirectional propagated changes may occur by even a slight modification of an observation. A multi-objective memetic approach considering time-dependent transition time (called MOMA-TD) is proposed to address the time-dependent characteristics and NP-hardness. The MOMA-TD combines the multi-objective memetic algorithm (MOMA) with problem-specific crossover, mutation, and local search operators to improve the efficiency and to enhance the exploitation. The highlights of this study are as follows: 1) the proposal of a MOMA-based framework for addressing the time-dependent MO-AEOSSP; 2) the design of two problem-specific crossover operators and a time-dependent local search operator. A domination-based MOMA-TD (D-MOMA-TD) and an indicator-based MOMA-TD (I-MOMA-TD) are examined and compared with several classical algorithms: NSGA-II, MOEA/D, IBEA, SPEA2. Experimental results on 5 different multi-orbit scenarios show that the MOMA-TDs outperform the comparative methods in terms of convergence, solution quality and distribution, providing the time-dependent MO-AEOSSP with a much more practical and appliable approach.