The satellite image downlink scheduling problem (SIDSP) is included in satellite mission planning as an important part. A customer demand is finished only if the corresponding images are eventually downloaded. Due to the growing customer demands and the limited ground resources, SIDSP is an oversubscribed scheduling problem. In this paper, we investigate SIDSP with the case study of China’s commercial remote sensing satellite constellation (SuperView-1) and exploit the serial scheduling scheme for solving it. The idea is first determining a permutation of the downlink requests and then producing a schedule from the given ordered requests. A schedule generation algorithm (SGA) is proposed to assign the downlink time window for each scheduled request according to a given request permutation. A hybrid genetic algorithm (HGA) combined with neighborhood search is proposed to optimize the downlink request permutation with the purpose of maximizing the utility function. Experimental results on six groups of instances with different density demonstrate the effectiveness of the proposed approach.

A decomposition-based optimization algorithm was proposed for solving Earth Observation Satellites scheduling problem. The problem was decomposed into task assignment main problem and single satellite scheduling sub-problem. In task assignment phase, the tasks were allocated to the satellites, and each satellite would schedule the task respectively in single satellite scheduling phase. We adopted an adaptive ant colony optimization algorithm to search the optimal task assignment scheme. Adaptive parameter adjusting strategy and pheromone trail smoothing strategy were introduced to balance the exploration and the exploitation of search process. A heuristic algorithm and a very fast simulated annealing algorithm were proposed to solve the single satellite scheduling problem. The task assignment scheme was valued by integrating the observation scheduling result of multiple satellites. The result was responded to the ant colony optimization algorithm, which can guide the search process of ant colony optimization. Computation results showed that the approach was effective to the satellites observation scheduling problem.

Simultaneously optimizing monetary cost and makespan of workflow execution is substantial to enhance the competitiveness of cloud services, but it still imposes challenges. Heuristics-based algorithms are often problem-dependent and well-suitable for special cases, but the complexity of workflow structures seriously challenges their generalization. Metaheuristics-based algorithms pose good generalization, but the elasticity and heterogeneity of cloud resources seriously impact their search efficiency. Inspired by previous works, we tailor a memetic workflow scheduling algorithm (KDMA for short) that embeds a heuristic local search operator into the multi-objective metaheuristic algorithm to combine their strengths and complement each other's shortcomings. Specifically, the proposed local search operator searches for a set of solutions with good convergence and diversity by accumulating tasks one by one. This operator is good at gathering workflow tasks into a limited range of candidate resources, thereby guiding the metaheuristic algorithm to focus on exploring potential solution regions. Moreover, KDMA includes an adaptive strategy to determine the number of solutions reproduced by the problem-special local search operator based on its past overall contribution. We compare KDMA to five representative algorithms over 25 real-world workflow instances to corroborate its superior all-around performance by performing the best on 21 workflow instances. Meanwhile, we conduct an ablation analysis to verify the performance contributions of two proposed mechanisms.

The past decade has seen an increase in the number of satellites in orbit and in highly dynamic satellite requests, making the control by ground stations inefficient. The traditional management composed of ground planning with separate onboard execution is seriously lagging in response to dynamically incoming tasks. To meet the demand for the real-time response to emergent events, a multi-autonomous-satellite system with a central-distributed collaborative architecture was formulated by an integer programming model. Based on the structure, evolutionary rules were proposed to solve this problem by the use of sequence solution construction and a constructed heuristic method based on gene expression programming evolution. First, the features of the problem are extracted based on domain knowledge, then, the problem-solving rules are evolved by gene expression programming. The simulation results reflect that the evolutionary rule completely surpasses the three types of heuristic rules with adaptive mechanisms and achieves a solution effect close to meta-heuristic algorithms with a reasonably fast solving speed.

Small satellite image downlink scheduling problem (SSIDSP) is an important part of satellite mission planning. SSIDSP mainly needs to balance how to better match the limited receiving capacity of the ground station with the limited satellite resources. In this paper, regional targets are considered with SSIDSP. We propose a mathematical model that maximizes profit by considering time value and regional targets. A downlink schedule algorithm (DSA) is proposed to complete the task sequence arrangement and generate scheduling results. A heuristic genetic algorithm (HGA) is used to optimize the generated task sequence to achieve higher profit. Three scale test instances are used to test the effectiveness of HGA and DSA. We compare the effect of HGA, basic genetic algorithm (GA), and construction heuristic algorithm. The experimental results proved that the proposed approach ensures the successful completion of observation tasks and is effective for SSIDSP.