Maximum Profit Heuristic Algorithm for Earth Observation Satellites Scheduling Problem

Earth observation satellite scheduling problem (EOSSP) is a challenging NP-hard problem in the aerospace field, which aims to develop tasks execution sequences for all earth observation satellites (EOSs) to maximize the aggregate profit from all tasks. As the number of EOSs and tasks continues to grow, ground crews face the constant challenge of effectively managing all the satellites, emphasizing the need of for a fast and efficient algorithm. However, existing algorithms are often time-consuming to construct a satisfactory solution for EOSSP. To overcome the deficiency in existing algorithms, this paper proposes a fast and efficient maximum profit heuristic algorithm (MPHA). To fast construct an optimal solution for EOSSP, the proposed MPHA involves three novel designs. Firstly, a problem reconstruction strategy is proposed to narrows the search space, so as to reduce the problem complexity. Secondly, a maximum profit guided window selection strategy is proposed to find a high quality initial solution. Lastly, a maximum profit guided solution reconstruction strategy is proposed to legalize the solution with as little reduction in aggregate profit as possible. Through these three strategies, the MPHA can quickly find an approximate optimal solution for EOSSP. Extensive experiments results indicate the MPHA is capable of achieving superior performance in terms of both solution quality and running time. And compared with the state-of-the-art algorithms, the aggregate profit obtained by the MPHA increased by 7.5% on the large-scale EOSSP.