Learning-Based Deadlock-Free Multi-Objective Task Offloading in Satellite Edge Computing With Data-Dependent Constraints and Limited Buffers

Satellite edge computing (SEC) is important for future network deployments because of its global coverage and low-latency computing services. Nevertheless, due to data dependencies among tasks and limited buffers in satellites, a coupling exists between transmission and computation, and undesired <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">deadlocks</i> may arise. This paper addresses task offloading in SEC and aims to minimize service latency, energy consumption, and time window violations simultaneously. First, a mixed-integer nonlinear programming model is presented. To resolve potential deadlocks, a deadlock amending algorithm (DAA) based on Petri net with polynomial time complexity is proposed. Deadlocks in solutions are amended by finding a transition sequence that corresponding transmission and computation can be performed sequentially. By embedding DAA, we develop a learning-based deadlock-free multi-objective scheduling algorithm (LDMOSA) that combines the exploration of evolutionary algorithms with the perception of reinforcement learning. To enhance the convergence and diversity of solutions, an initialization strategy employing problem-specific constructive heuristics is designed. Then, a learning-based mechanism is used to leverage real-time information to perform adaptive operator selection during the search process. Finally, extensive experiments demonstrate the effectiveness of DAA in resolving deadlocks, and the LDMOSA outperforms state-of-the-art algorithms for task offloading in SEC.