Three-stage hybrid scheduling method based on link adjustment and arc replacement for large-scale satellite ground station resource scheduling considering idleness rate - Shunyi Cao; Xiaolu Liu; Lei He (Results in Engineering)
With the rapid growth of satellite applications and the integration of Tracking, Telemetry, and Command (TTC) and Digital Data Transmission (DDT) devices, large-scale integrated scheduling of heterogeneous tasks has become critical yet challenging due to resource scarcity and complex constraints. This paper addresses the Large-scale Integrated Scheduling Problem of TTC and DDT (LISP-TTC&DDT) which aims to maximize task completion rates and to optimize idleness rate. We propose the Local Search Algorithm Based on Link-adjustment and Local-tabu (LSA-LALT), which employs a three-stage optimization framework. Firstly, a Link-adjustment-based Optimization Operator (LAOO) resolves task-resource conflicts through iterative conflict propagation and rescheduling, optimizing the completion rate of DDT tasks first and then proceeding to optimize the completion rate of TTC tasks. Then, a Local-tabu Optimization Operator Based on Arc Replacement (LTOO-AR) enhances the idleness rate by replacing task arcs while introducing a local-tabu strategy to prevent the algorithm from becoming trapped in local optima. Experimental validation on the 4th Tianzhi Cup dataset demonstrates LSA-LALT's superiority over state-of-the-art algorithms across ten scenarios with up to 28544 tasks. The proposed algorithm showcases its potential for real-world satellite-ground resource management.