Abstract

Translate

This paper proposes a scheduling approach for multi-type spacecraft operational tasks that can be interleaved, considering constrained space–ground telemetry, tracking, and command (TT&C) resources, as well as task splitting. A mixed-integer linear programming model is formulated to maximize the total task completion reward under service time-window constraints for splittable and unsplittable routine tasks, continuous tracking requirements, coupling relationships between routine and continuous tracking tasks, temporal logic dependencies, visibility constraints, and non-overlapping scheduling conditions. To improve solution efficiency and scheduling performance, a heuristic algorithm that combines priority rules with partial backtracking is developed. Task priorities are determined based on completion rewards, due times, execution durations, and temporal relationships, and scheduling is refined to avoid conflicts with predefined constraints. A partial backtracking mechanism guided by task release times enables effective adjustment when TT&C requirements cannot be satisfied. Comparative experiments with CPLEX and four heuristic algorithms validate the effectiveness of the proposed method.

Full text

Turn on search term navigation

Translate

1. Introduction

The complexity of space missions has increased markedly, driven by rapid advances in space technology and the growing number of sophisticated spacecraft in low-Earth orbit [1]. A representative example is the long-term operation of a space station, which requires a broad range of tasks. These tasks include orbit maintenance, inspections of both crewed and cargo spacecraft [2], and the execution of major space science experiments and applications [3,4]. To manage these requirements, the operational task planning for the Chinese Space Station (CSS) is structured into a five-stage hierarchy. This process progresses from long-term to short-term and from high-level to detailed planning. The hierarchy comprises long-term planning, mid-term planning, flight mission planning, monthly planning, and implementation planning. Long-term, mid-term, and flight mission planning address scheduling activities across multiple mission cycles. Monthly planning provides a preliminary outline of operations, while implementation planning focuses on precise scheduling within specific time intervals and is critical for ensuring the successful execution of spacecraft operational tasks [5].

In implementation planning, space–ground telemetry, tracking, and command (TT&C) resources are essential for enabling ground operations teams to monitor, communicate with, and control spacecraft, forming the foundation for reliable mission execution [6,7]. During this process, high-level objectives are translated into executable operational tasks comprising specific activities or command sequences, coordinated with the scheduling of TT&C resources. TT&C resources primarily include tracking and data relay satellites (TDRSs) and ground-based TT&C stations (GSs). Their available TT&C time windows constitute key assets for task execution. Relay satellites in geostationary orbit provide extended tracking durations, whereas ground-based TT&C stations offer limited coverage due to their geographic location and the Earth’s curvature. For instance, a spacecraft in a 500 km circular orbit can be supported by relay satellites for more than 40% of its orbit, whereas ground-based TT&C stations provide less than 3% coverage [8,9].

Spacecraft operational tasks can be classified into continuous tracking tasks and routine tasks based on the required duration of TT&C activities. Continuous tracking tasks, such as space lectures or orbital control, require uninterrupted tracking and data transmission across multiple TT&C stations, often over extended periods. Routine tasks are generally shorter and are typically completed within a single TT&C time window, such as data injection or payload data downlink. Some routine tasks require continuous data transmission and cannot be split, whereas others comprise sequential sub-events with strict timing constraints that may span multiple TT&C time windows. An example is a space station experiment with equipment power-up, data transmission, and shutdown steps, each separated by several hours.

Traditional mission scheduling models often assume tasks are unsplittable, overlooking the modularity and temporal dependencies of sub-events. In practice, allowing sub-events to be executed in an interleaved manner across TT&C time windows enables parallel execution of tasks on a spacecraft, improving resource use and task completion. Effective spacecraft operations must therefore ensure uninterrupted tracking for continuous tasks and schedule splittable routine tasks efficiently to maximize the overall task completion rate.

As illustrated in Figure 1, within the planning interval from 8:00 to 12:00, three relay satellites (TDRS East, TDRS Middle, TDRS West) and two ground-based TT&C stations (GS1, GS2) provide TT&C time windows for a spacecraft performing five tasks: routine tasks T1–T2, splittable routine tasks T3 and T5, and continuous tracking task T4. Task T2 must begin within 15 min of the completion of T1, while T4 requires more than one hour of uninterrupted tracking. The subtasks of T3 (T3a, T3b) and T5 (T5a–T5c) must be executed sequentially. Using a heuristic strategy (e.g., scheduling tasks with earlier release times first), scheduling T3 as an unsplit task on TDRS East forces T2 to be executed on GS1. In contrast, splitting T3 allows interleaving with T2, reducing the required TT&C time window. Similarly, if T5 cannot be split, sub-task T5c may miss available time windows. Splitting T5 allows T5a–T5b to be scheduled on TDRS East and T5c on GS2, improving task completion.

In this study, we develop a mixed-integer linear programming (MILP) model to maximize the total reward of completed operational tasks under constrained TT&C resources. The model incorporates service time-window constraints for splittable and unsplittable routine tasks, continuous tracking constraints, coupling relationships between routine and continuous tracking tasks, temporal logic dependencies, visibility constraints, and non-overlapping scheduling conditions. To enhance solution quality and computational efficiency, we propose a heuristic algorithm that combines priority rules with partial backtracking. Task priorities are determined by rewards, due times, execution durations, and temporal relationships. A rollback mechanism based on task release times enables effective backtracking when TT&C constraints cannot be satisfied. The performance of the proposed algorithm is evaluated against CPLEX and four heuristic algorithms, demonstrating its effectiveness and efficiency.

The remainder of this paper is organized as follows: Section 2 reviews related studies; Section 3 formulates the problem and presents the MILP model; Section 4 introduces the proposed heuristic algorithm; Section 5 reports numerical experiments and performance analysis; and Section 6 concludes the study with a summary and discussion.

2. Literature Review

Related studies on spacecraft task planning and scheduling in complex operational environments mainly focus on two aspects: space station task planning and satellite TT&C task scheduling.

2.1. Space Station Task Planning

In space station task planning, major spacefaring nations have conducted extensive research and have developed a variety of operational planning systems, including integrated planning systems [10], short-term planning viewers [11], execution tools such as Playbook [12], and rule-based scheduling systems such as ASPEN [13]. Publicly available studies, however, largely concentrate on medium- to long-term or monthly planning, with limited attention to the detailed scheduling of diverse operational tasks during implementation. Lin et al. [14] examined long-term task planning for in-orbit experiment arrangements, crew rotation, and logistics, proposing a three-layer decomposition framework for modeling and solution. Zhu and Luo [15] developed a hybrid approach combining multi-objective evolutionary algorithms with differential evolution to optimize space station logistics strategies. Zhang et al. [16] investigated spacecraft launch time and loading optimization under multiple constraints using a two-level optimization algorithm. Bu et al. [17] addressed payload and astronaut task planning through multi-objective and constraint satisfaction models solved via an NSGA-II algorithm. Bu et al. [18] also developed a constraint satisfaction model for monthly space station task planning and proposed an iterative conflict resolution algorithm that includes solution strategies for equipment usage constraints and task precedence relationships. Mu et al. [19] studied daily re-planning of on-orbit activities during the implementation phase, considering astronauts’ schedules, time dependencies between activities, and onboard resource constraints, and employed a time-backtracking iterative strategy to generate re-planning solutions. Marquez et al. [20] examined how task complexity affects astronauts’ performance, workload, and situational awareness. They considered constraints such as planning deadlines, onboard resource needs, and temporal relationships and analyzed how task complexity affects scheduling performance.

In summary, existing studies of space station task planning mainly focus on system design and mid- to long-term mission planning. Research on the on-orbit implementation phase is limited. Current studies primarily address the scheduling of astronauts’ daily on-orbit activities, but they do not consider ground-based operations planning for TT&C activities. Previous studies also do not account for constraints such as TT&C time windows, different types of tracking tasks (e.g., long-duration tracking or tasks that can be split), and the scheduling of tasks within those time windows. Therefore, the spacecraft operations planning problem that considers TT&C time windows and task splitting remains insufficiently addressed.

2.2. Satellite TT&C Task Scheduling

In satellite TT&C task scheduling, some studies focus on communication between ground-based TT&C stations and satellites, particularly for data downlink. Karapetyan et al. [21] investigated data downlink scheduling between ground-based TT&C stations and Earth observation satellites and proposed a two-stage heuristic algorithm. Spangelo et al. [22] formulated a MILP model for single-satellite, multi-ground-station communication scheduling to maximize data throughput and developed an iterative solution algorithm. Zhang et al. [23] established a mathematical model for satellite TT&C task scheduling aimed at minimizing task completion time and proposed an ant colony optimization algorithm. Chen et al. [24] developed a mathematical programming model for TT&C task scheduling with multiple satellites and multiple ground-based TT&C stations and designed a genetic algorithm based on population disturbance and elimination strategies. Liu et al. [25] studied multi-satellite, multi-ground-station downlink scheduling that accounts for task waiting times and proposed a simulated annealing algorithm incorporating tabu lists and start-time optimization.

Other studies focus on optimizing TT&C task scheduling for relay satellites. Fang et al. [26] developed a constraint programming model for the single-access link scheduling problem and designed a genetic algorithm. Wu et al. [27] proposed a relay satellite TT&C model that allows users to submit multiple service time windows, select preferred antennas, and specify expected execution times for each task. They formulated a mathematical model to maximize task completion rates and meet user expectations and designed an iterative task scheduling algorithm to resolve conflicts. Hou et al. [28] examined Earth-to-space link planning considering link switching, routing updates, and relay satellite configurations and developed a corresponding link planning algorithm. Li et al. [7] applied deep reinforcement learning to antenna scheduling in data relay satellite networks. Some relay satellite TT&C scheduling studies also consider task splitting. Chen et al. [29] investigated the TT&C resource scheduling for relay satellites in the context of breakpoint transmission and developed a hybrid algorithm integrating adaptive variable neighborhood descent with tabu list mechanisms. Li et al. [30] studied the breakpoint-resume operation mode in relay satellite scheduling. They established a model for scheduling monostatic antennas to support resumable data transmission and designed a two-stage algorithm incorporating breakpoint resumption strategies. Liu et al. [31] proposed a two-stage insertion heuristic algorithm for dynamic antenna installation times and splittable tasks. Deng et al. [32] explored task splitting in dynamic relay satellite scheduling and developed a preemptive dynamic algorithm that accommodates both task preemption and splitting.

Most existing satellite TT&C task scheduling research focuses on homogeneous tasks, such as data downlink, and does not address the sequencing or interleaved execution of heterogeneous tasks within the same TT&C time window. In contrast, spacecraft operations require the coordination of heterogeneous tasks, including data upload, data download, long-duration continuous tracking, and split tracking tasks. Each task type has different requirements, adding complexity to the scheduling process. Moreover, previous work generally considers simple time-conflict constraints, while spacecraft operational scheduling must manage more complex temporal and resource constraints. Continuous tracking tasks require uninterrupted tracking across multiple TT&C time windows. Routine or splittable tasks must avoid overlapping within shared TT&C time windows. Temporal and logic relationships, as well as visibility constraints, further increase scheduling complexity and complicate conflict detection and constraint satisfaction.

As shown in Table 1, we compare major work on space station task planning and satellite TT&C task scheduling with the features considered in this study. It is evident that research on multi-task scheduling for complex spacecraft operations, such as space stations, that incorporate TT&C resources and task splitting remains limited. Scheduling problems that require handling space–ground TT&C time windows, continuous tracking, temporal and logic constraints, the interleaving of multiple tasks within the same TT&C time window, and task splitting continue to present important challenges.

3. Mathematical Programming Model

3.1. Problem Description

During orbital operations, large and complex spacecraft, such as space stations, must continuously receive TT&C commands from ground operations or transmit spacecraft data to the ground operations and planning department (GOPD) through ground-based and space-based TT&C resources. The main optimization goal of the GOPD is to maximize the completion reward of various types of operational tasks for a single complex spacecraft during the planning cycle.

In this problem, a group of ground-based TT&C stations and TDRSs, denoted as $M$ , is responsible for observing multiple operational tasks with varying requirements from a complex spacecraft in orbit. Due to orbital dynamics and the spatial distribution of TT&C resources, each station $m \in M$ can observe the spacecraft only during limited visibility periods, forming TT&C time windows within a planning cycle. The $k^{t h}$ available TT&C time window for station $m$ is denoted by $[t_{m}^{s t a r t (k)}, t_{m}^{e n d (k)}]$ , with the set of all available TT&C time windows for station $m$ represented by $K_{m}$ , and the set of all TT&C time windows across stations represented by $K$ . The spacecraft operational tasks can be categorized into two types: routine tasks ( $N_{a})$ and continuous tracking tasks ( $N_{b})$ . The set $N$ denotes all tasks in complex spacecraft, where $N = N_{a} \cup N_{b}$ .

Some routine tasks cannot be split because they require continuous data transmission, while others that include multiple operational stages can be divided into ordered subtasks. To ensure safe and reliable execution, GOPD typically pre-split tasks based on command breakpoints and the positions of key commands. For example, a task $i \in N_{a}$ with two command breakpoints and one critical command may be divided into three sub-events: preparation, key event, and completion, denoted as $t_{1}^{i}$ , $t_{2}^{i}$ , and $t_{3}^{i}$ . Precedence relationships are defined to ensure sequential execution. For simplicity, all sub-events and commands are referred to as subtasks in the remainder of this paper. The set of subtasks for task $i \in N_{a}$ is denoted by $T_{i} = {t_{1}^{i}, t_{2}^{i}, \dots, t_{q}^{i}}$ , and the set of all routine subtasks is denoted by ${\bar{N_{a}} = \cup}_{i \in N_{a}} T_{i}$ . The number of all subtasks for task $i \in N_{a}$ is denoted by $c_{i}$ , where $c_{i} = c a r d (T_{i})$ . Each task $i \in N$ is subject to strict release-to-due time window $[{s t}_{i}, {e t}_{i}]$ , and subtasks inherit the release-to-due interval of their parent task. The split routine task set $\bar{N_{a}}$ and the continuous tracking task set $N_{b}$ are combined into $\bar{N}$ , representing all tasks to be scheduled. The processing time of task $i$ is denoted by $p_{i}$ , where $i \in \bar{N}$ .

Two types of temporal constraints are considered: precedence constraints, which define execution order and are denote by $E = {(i, j) | i, j \in \bar{N}}$ , and precedence constraints with fixed time intervals, which specify mandatory temporal gaps between dependent tasks and are denote by $G = {(i, j, g_{i j}, h_{i j}) | i, j \in \bar{N}}$ . To express temporal relationships that require fixed intervals, we introduce the parameters $g_{i j}$ and $h_{i j}$ , These represent the earliest start time and the latest end time for task $j$ after task $i$ finishes. For example, after completing task $i$ , the shutdown task $j$ must begin at least $g_{i j}$ seconds later, or it must finish within $h_{i j}$ seconds. Subtasks inherit the parent task’s temporal relationships. In an orbit control task $j \in N_{a}$ , sub-task $j_{1}$ (attitude adjustment) must precede sub-task $j_{2}$ (orbit adjustment), and both must follow the completion of task $i \in N_{a}$ . Furthermore, there are mutual-exclusion logic relationships $L = {(i, j) | i, j \in \bar{N}}$ between some tasks. Tasks such as data injection $i$ and its backup $j$ cannot occupy the same TT&C time window.

The completion of each task yields a corresponding reward $β_{i}$ , defined by its priority level. A routine task yields a reward only when all its subtasks are completed. All notations commonly used in the problem formulation are listed in Table 2.

3.2. Problem Assumption

Given the multiple constraints and the high complexity of real-world engineering applications, it is necessary to translate these practical issues into well-defined scientific problems. In this problem, we make the following assumptions:

(1) . Antenna elevation angle: Each ground-based TT&C station and each TDRS is treated as a single TT&C station equipped with an appropriate antenna. The elevation angle of each ground-based TT&C station and TDRS observing the spacecraft is determined by the spacecraft’s orbit and the station’s geographic location. Each ground-based TT&C station or TDRS periodically enters the spacecraft’s field of view, with certain rare exceptional circumstances not considered [33,34].

(2) . Frequency conflicts: We assume that the spacecraft carries antennas that support different frequency bands (e.g., S and Ka/Ku bands), enabling communication with multiple ground-based TT&C stations and TDRSs. This assumption is based on the experience gained from managing complex spacecraft in operation. For example, both the International Space Station and the China Space Station operate with multiple antenna types and frequency bands [34,35]. The communication frequency band between the spacecraft and each station is fixed, with no frequency conflicts [34,35].

(3) . Continuous Tracking: Due to the limited number and geographic distribution of ground-based TT&C stations, continuous tracking tasks can only be supported by adjacent relay satellites, with the spacecraft maintaining synchronization across multiple relay satellites. GOPD is responsible for coordinating resource allocation among these satellites to satisfy the frequency and bandwidth requirements of continuous tracking tasks [36]. The GOPD coordination process is outside the scope of this study. Continuous tracking tasks are critical and must maintain stable communication with ground control; thereby, they are unsplittable.

(4) . Temporal relationship: Continuous tracking tasks are constrained only by precedence relationships, whereas routine tasks also must satisfy specified temporal intervals.

(5) . Link establishment process: TT&C time windows already account for link establishment, and, the window start time marks the task’s execution start.

(6) . Other: Spacecraft onboard resources are assumed sufficient; energy and astronaut constraints are incorporated into the task’s time windows and temporal conditions.

3.3. Available TT&C Interval Calculation

To generate the available TT&C interval for each task, this study adopts the following process:

(1) For a routine task’s subtask $i (i \in \bar{N_{a}})$ , the available TT&C interval is obtained by taking the intersection between the spacecraft’s TT&C time window $k$ , defined as $[t_{m}^{s t a r t (k)}, t_{m}^{e n d (k)}]$ , and the subtask’s release and due window $[{s t}_{i}, {e t}_{i}]$ . The intersection determines the available interval for execution.

(1) ${[r}_{i k}, d_{i k}] = [t_{m}^{s t a r t (k)}, t_{m}^{e n d (k)}] \cap [{s t}_{i}, {e t}_{i}]$

(2) For a continuous tracking task $i (i \in N_{b})$ , this study generates a continuous tracking plan $U_{i}$ as described in Appendix A. Based on the generated plan, the available TT&C intervals for task $i$ are determined. When the $f^{t h}$ feasible continuous tracking plan for task $i$ , denoted as $u_{i}^{f} = {k_{1}^{f}, ⃯, k_{n}^{f}}$ , is obtained, the available TT&C time window for plan $u_{i}^{f}$ is determined by taking the intersection of the start time window of $k_{1}^{f}$ and the end time window of $k_{n}^{f}$ with the release and due time window $[{s t}_{i}, {e t}_{i}]$ , as follows:

(2) $[t_{u_{i}^{f}}^{s t a r t}, t_{u_{i}^{f}}^{e n d}] = {[t}_{m}^{s t a r t (k_{1}^{f})}, t_{m}^{e n d (k_{n}^{f})}] \cap [{s t}_{i}, {e t}_{i}]$

3.4. Model Establishment

Table 3 presents the model variables used in this study.

The objective is to maximize the reward derived from the completed tasks. In this problem, the reward $β_{i}$ is the coefficient weight obtained after completing task $i \in \bar{N}$ . The first term of objective Function (3), $\sum_{i \in N_{a}} β_{i} m a x {\sum_{m \in M} \sum_{k \in K} \sum_{j \in T_{i}} x_{i j}^{m k} - c_{i} + 1,0}$ , represents the reward of completing all subtasks of a routine task, i.e., the reward is only obtained once all the split subtasks of a routine task are completed. The second term of the objective Function (3), $\sum_{i \in N_{b}} \sum_{u \in U_{i}} β_{i} z_{i}^{u}$ , represents the reward earned when a continuous tracking task is successfully scheduled into a feasible continuous tracking plan.

(3) $m a x \sum_{i \in N_{a}} β_{i} m a x {\sum_{m \in M} \sum_{k \in K} \sum_{j \in T_{i}} x_{i j}^{m k} - c_{i} + 1,0} + \sum_{i \in N_{b}} \sum_{u \in U_{i}} β_{i} z_{i}^{u}$

(1) Each routine subtask $j \in T_{i} (i \in N_{a})$ can be assigned to a station’s TT&C time window at most once:

(4) $\sum_{m \in M} \sum_{k \in K_{m}} x_{i j}^{m k} \leq 1, \forall i \in N_{a}, j \in T_{i}$

(2) Each continuous tracking task $i \in N_{b}$ can be assigned to at most one continuous tracking plan capable of servicing the task:

(5) $\sum_{u \in U_{i}} z_{i}^{u} \leq 1, \forall i \in N_{b}$

Constraints (4) and (5) together restrict the service assignments for both routine and continuous tracking tasks so that each task can be serviced only once.

(3) If a continuous tracking plan $u \in U$ uses multiple TT&C time window, these time windows within the plan cannot be reused for routine subtasks. Here, $M$ is a very large number:

(6) $\sum_{m \in M} \sum_{k \in u} \sum_{i \in N_{a}} \sum_{j \in T_{i}} x_{i j}^{m k} \leq M (1 - \sum_{i \in N_{b}} z_{i}^{u}), \forall u \in U$

Constraint (6) ensures no conflicts in TT&C time window assignments by preventing a time window allocated to a continuous tracking plan from being used for a routine task.

(4) The start TT&C time $ξ_{j}$ of the routine subtask $j \in T_{i}$ ( $i \in N_{a}$ ) must not precede the start time of the TT&C time window allocated to this subtask.:

(7) $ξ_{j} - x_{i j}^{m k} r_{j k} \geq 0, \forall i \in N_{a}, j \in T_{i}, m \in M, k \in K_{m}$

(5) The start TT&C time $ξ_{j}$ of the routine subtask $j \in T_{i}$ ( $i \in N_{a}$ ), plus the duration of the subtask, must not exceed the end time of the available TT&C time window allocated this subtask:

(8) $ξ_{j} - x_{i j}^{m k} d_{j k} + p_{j} x_{i j}^{m k} - M (1 - x_{i j}^{m k}) \leq 0, \forall i \in N_{a}, j \in T_{i}, m \in M, k \in K_{m}$

Constraints (7) and (8) restrict the execution times of the routine tasks.

(6) The start TT&C time $ξ_{i}$ of the continuous tracking task $i \in N_{b}$ must not occur earlier than the start time of the feasible continuous tracking plan allocated to this task:

(9) $ξ_{i} - z_{i}^{u_{i}^{f}} t_{u_{i}^{f}}^{s t a r t} \geq 0, \forall i \in N_{b}, u_{i}^{f} \in U_{i}, f \in F_{i}$

(7) The start TT&C time $ξ_{i}$ of the continuous tracking task $i \in N_{b}$ , plus the duration of the task, must not exceed the end time of the feasible continuous tracking plan allocated to this task:

(10) $ξ_{i} - z_{i}^{u_{i}^{f}} t_{u_{i}^{f}}^{e n d} + p_{i} z_{i}^{u_{i}^{f}} - M (1 - z_{i}^{u_{i}^{f}}) \leq 0, \forall i \in N_{b}, u_{i}^{f} \in U_{i}, f \in F_{i}$

Constraints (9) and (10) restrict the execution times of the continuous tracking tasks.

(8) If routine subtasks $l, j \in \bar{N}$ are tracked by a certain TT&C station, then there is only one tracking sequence order:

(11) $\sum_{m \in M} (f_{l j}^{m} + f_{j l}^{m}) \leq 1, \forall j, l \in \bar{N}, l \neq j$

(9) If the routine subtasks $l, j \in \bar{N}$ are tracked during the tracking time window $k$ of the station m, then the tasks $l, j$ have a unique precedence order. This constraint can be expressed by the following formula: $f_{l j}^{m} + f_{j l}^{m} = \sum_{m \in M, k \in u} x_{i j}^{m k} \times \sum_{m \in M, k \in u} x_{i l}^{m k}, \forall j, l \in \bar{N}, m \in M, k \in K$ . After linearization, this can be represented by Formulas (12)–(14):

(12) $f_{l j}^{m} + f_{j l}^{m} \leq \sum_{k \in K_{m}} x_{i l}^{m k}, \forall i \in N_{a}, j, l \in \bar{N_{a}}, l \neq j, m \in M$

(13) $f_{l j}^{m} + f_{j l}^{m} \leq \sum_{k \in K_{m}} x_{i j}^{m k}, \forall i \in N_{a}, j, l \in \bar{N_{a}}, l \neq j, m \in M$

(14) $f_{l j}^{m} + f_{j l}^{m} \geq \sum_{k \in K_{m}} x_{i l}^{m k} + \sum_{k \in K_{m}} x_{i j}^{m k} - 1, \forall i \in N_{a}, j, l \in \bar{N_{a}}, l \neq j, m \in M$

Constraints (11)–(14) define precedence relationships when different routine tasks are serviced by the same TT&C station. Constraints (12)–(14) indicate that if multiple tasks are scheduled within the same TT&C time window, station-level sequencing is required to ensure that tasks are tracked in the correct order.

(10) The start times of routine subtasks $l$ and $j$ tracked by the same TT&C station $m$ are sequentially related and can be expressed by either Formula (15) or (16):

(15) $ξ_{l} - ξ_{j} \geq p_{l} f_{l j}^{m} - (M - p_{l}) (1 - f_{l j}^{m}), \forall i \in N_{a}, j, l \in \bar{N_{a}}, l \neq j, m \in M$

(16) $ξ_{j} - ξ_{l} \geq {p_{j} f}_{j l}^{m} - (M - p_{j}) (1 - f_{j l}^{m}), \forall i \in N_{a}, j, l \in \bar{N_{a}}, l \neq j, m \in M$

Constraints (15)–(16) define the relationship between the start times of routine tasks and their service order at the same TT&C station.

(11) A “precedes” temporal relationship or a “precedes with a fixed time interval” relationship may exist between the start times of routine subtasks $l$ and $j$ :

(17) $ξ_{l} + p_{l} \leq ξ_{j}, \forall j, l \in \bar{N}, j \neq l, (j, l) \in E$

(18) $ξ_{l} + p_{l} + g_{l j} \leq ξ_{j}, \forall j, l \in \bar{N_{a}}, l \neq j, (l, j, g_{l j}, h_{l j}) \in G$

(19) $ξ_{j} + p_{j} \leq ξ_{l} + p_{l} + h_{l j}, \forall j, l \in \bar{N_{a}}, l \neq j, (l, j, g_{l j}, h_{l j}) \in G$

Constraints (17)–(19) express the temporal relationships between tasks.

(12) A logical relationship exists between routine subtasks $l$ and $j$ that prevents them from being scheduled within the same TT&C time window:

(20) $x_{i j}^{m k} + x_{i l}^{m k} \leq 1, \forall i \in N_{a}, j, l \in \bar{N_{a}}, i \neq l, (j, l) \in L, m \in M, k \in K_{m}$

Constraint (20) defines the mutual exclusion logic between tasks within the same TT&C time window.

(13) Constraints (21)–(24) represent the value ranges for the decision variables $x_{i j}^{m k}$ , $z_{i}^{u}$ , $f_{l j}^{m}$ , and $ξ_{i}$ :

(21) $x_{i j}^{m k} \in {0,1}, \forall i \in N_{a}, j \in T_{i}, m \in M, k \in K_{m}$

(22) $z_{i}^{u} \in {0,1}, \forall i \in N_{b}, u \in U$

(23) $f_{i j}^{m} \in {0,1}, \forall i, j \in \bar{N}, m \in M$

(24) $ξ_{i} \in Z^{+}, \forall i \in \bar{N}$

Due to Constraints (11)–(13), scheduling multiple routine tasks or subtasks within a single TT&C time window to maximize total reward across all TT&C time windows. If each corresponding TT&C station is treated as a machine, this problem can be reduced to a Parallel Machine Scheduling problem with Time Windows and Job Priorities (PMSTWTB). Since PMSTWTB is NP-hard [37], the model in this study is also NP-hard. In addition, Constraint (6), which prevents conflicts between continuous tracking and routine tasks, and the nonlinear reward function for split tasks in (3), together with the large-M terms in Constraints (6), (8), (10), (15) and (16), make the model difficult for CPLEX to solve efficiently [38]. To address this challenge, we propose a heuristic algorithm based on task priority and partial backtracking search.

4. Priority-Based and Partial Backtracking Heuristic Algorithm

In spacecraft task scheduling, allocating multiple pending tasks within limited TT&C time windows under complex constraints such as space–ground TT&C resource limitations, temporal dependencies, and the coupling between continuous tracking and routine tasks constitutes a resource allocation problem with time-window constraints. This problem features complex temporal dependencies and inter-task coupling, making it an NP-hard combinatorial optimization problem. To address these challenges, this study proposes a heuristic task allocation approach that accounts for continuous tracking tasks, task splittability, and the nonlinear objective. A partial backtracking strategy is incorporated to enhance search flexibility. Drawing on the rollback mechanism in classical backtracking algorithms [39,40], the proposed method integrates priority-based heuristics with partial backtracking, forming a hybrid algorithm that balances computational efficiency and solution quality.

4.1. Algorithm Framework

The overall process of the proposed algorithm is illustrated in Figure 2. The algorithm begins by sorting pending tasks according to their release times. It then examines whether available TT&C time windows exist. If available windows are present, the algorithm proceeds; otherwise, it outputs the final schedule. Next, the algorithm checks whether any tasks remain unallocated. If so, the available TT&C time windows are sorted by their earliest start times, and the task allocation method described in Section 4.2 is applied to assign tasks to suitable windows. When allocation succeeds, the remaining TT&C time windows and pending task set are updated, after which the algorithm returns to check for available windows. If allocation fails, the algorithm enters the partial backtracking phase described in Section 4.3. In this phase, a rollback search is performed to identify feasible TT&C time windows for the current task. If the rollback task has already been scheduled, the algorithm returns to the update step. If the rollback search is completed and the task cannot be allocated, the task is skipped and TT&C resources are updated. The process continues until all time windows have been examined, after which the final scheduling plan is produced.

The proposed heuristic algorithm provides a unified scheduling framework that accommodates heterogeneous TT&C time windows and constraint types. It initially allocates tasks based on task priorities, resource utilization, TT&C time-window matching, and conflict-free assignment rules. For tasks that cannot be scheduled in the initial phase, a partial backtracking strategy based on task release times enables effective rollback and reassignment.

4.2. Priority-Based Heuristic Task Allocation Method

In the previous section, we introduced the core framework of the heuristic algorithm. A critical step in this process is scheduling the pending tasks and the determination the suitable TT&C time windows. This section presents a priority-based heuristic task allocation method, which consists of three stages: task selection, TT&C time window selection, and task allocation. Initially, tasks are selected based on their priority. Next, we propose a method for selecting TT&C time windows tailored to different task types, with the goal of minimizing the total number of TT&C time windows utilized. Finally, using the selected tasks and TT&C time windows, task allocation is performed, and resources are updated accordingly. The following sections will provide a detailed explanation of the steps involved in this heuristic algorithm.

4.2.1. Task Selection Methods

Consistent with most search algorithms, the effectiveness of heuristic task allocation methods depends largely on the quality of the recommendations provided by the heuristic strategy. Refs. [41,42] have demonstrated that when the sorting heuristic provides effective suggestions, the algorithm can quickly yield high-quality results. Accordingly, this study introduces a priority-based task selection function that follows the principle of prioritizing tasks with higher importance.

(1) Tasks with higher values are scheduled first.

(25) $T_{c u r} = i, w h e r e i {= a r g m a x}_{i \in N_{c u r}} (β_{i}), \forall i \in \bar{N}$

where

T_{c u r}

represents the selected task or subtask, and

N_{c u r}

represents the remaining tasks to be allocated, with

N_{c u r} \subseteq \bar{N}

In some cases, tasks may compete for the same TT&C time windows. To address this, we consider both the task’s duration and the characteristics of its due time when allocating tasks. As shown in Figure 3, task $T_{1}$ has three available TT&C time windows (GS1, GS2, GS3) within the release-to-due time window, while task $T_{2}$ has only one TT&C time window (GS1) within its release-to-due time window. If task $T_{1}$ is allocated to GS1 first, task $T_{2}$ , with its earlier due time and longer duration, will not fit into the remaining TT&C time windows. However, if task $T_{2}$ is scheduled first, task $T_{1}$ can be allocated to GS2. It is evident that, when priorities are equal, tasks with earlier due times and longer durations have more stringent requirements for TT&C time windows. Consequently, such tasks should be given higher priority in the scheduling process.

Based on the above analysis, this paper defines the following heuristic task scheduling function based on task due time and duration.

(2) When task reward values are equal, tasks with earlier due times are prioritized. Additionally, tasks or subtasks with longer durations are given higher priority.

(26) $T_{c u r} = i, w h e r e i {= a r g m i n}_{i \in N_{c u r}} ({e t}_{i}), \forall i \in \bar{N}$

(27) $T_{c u r} = i, w h e r e i {= a r g m a x}_{i \in N_{c u r}} (p_{i}), \forall i \in \bar{N}$

Moreover, within the set of splittable tasks, the subtasks of a given parent task typically exhibit clear temporal sequencing requirements. Violating this sequence can result in conflicts between tasks. Therefore, this study sorts the subtasks of the same parent task according to the temporal constraints specified in the sets $E$ and $G$ , prioritizing those subtasks with earlier temporal dependencies.

(3) When the parent tasks are the same, subtasks are scheduled based on their temporal sequence.

(28) $T_{c u r} = j_{1}, \forall i \in N_{a}, j_{1}, j_{2} \in T_{i}, (j_{1}, j_{2}) \in E o r (j_{1}, j_{2}, g_{j_{1} j_{2}}, h_{j_{1} j_{2}}) \in G$

4.2.2. TT&C Time Window Selection Methods

The second step of the heuristic task allocation method involves selecting TT&C time windows to maximize their efficient utilization. Similar to the heterogeneous bin-packing problem, Refs. [43,44] suggest that placing the largest items into the smallest feasible bins not only optimizes bin usage but also mitigates computational bottlenecks in subsequent steps, thereby reducing the total number of bins required. Building upon the heuristic selection method from Section 4.2.1, which incorporates task return values and subtask scheduling strategies, we dynamically calculate the remaining available TT&C time windows and their occupancy. Using an optimal TT&C time window matching strategy, we propose a heuristic function for selecting TT&C time windows.

For each task or subtask to be scheduled, we first identify the available TT&C time windows and determine how many tasks are already scheduled in each window. We then sort the TT&C time windows based on the number of tasks scheduled and allocate the task to the time window with the highest occupancy.

(1) Assign the tasks or subtasks to the TT&C time window with the highest number of tasks already scheduled.

(29) $W_{c u r}^{i} = \bar{k}, w h e r e \bar{k} = a r g {m a x}_{\bar{k}} (n_{\bar{k}}), \forall i \in \bar{N_{a}}, \bar{k} \in K^{i}$

where

W_{c u r}^{i}

denotes the TT&C time window selected for task

i

n_{\bar{k}}

is the number of tasks already scheduled in time window

\bar{k}

, and

K^{i}

represents the set of TT&C time windows that can serve task

i

, with

K^{i} \subseteq K

To optimize the use of TT&C time windows for continuous tracking tasks, we sort the available options for the currently served tasks and prioritize the one that uses the fewest TT&C time windows.

(2) Assign continuous tracking tasks to the continuous tracking plan that uses the fewer TT&C time windows.

(30) $U_{c u r}^{i} = U_{i}^{f}, w h e r e U_{i}^{f} = a r g {m a x}_{U_{i}^{f}} (n^{U_{i}^{f}}), \forall i \in N_{b}, U_{i}^{f} \in U_{i}$

where

U_{c u r}^{i}

denotes the TT&C plan selected for continuous tracking task

i

, and

n^{U_{i}^{f}}

represents the number of TT&C time windows used by the

f^{t h}

feasible continuous tracking plan for task

i

4.2.3. Task Allocation Method

The key steps for task allocation to TT&C time windows using the heuristic rules described above are as follows. The corresponding pseudocode is shown in Algorithm 1.

(1) Generate the set of available time windows for the task

First, based on the task selection method described in Section 4.2.1, the next task to be allocated is identified. The corresponding set of alternative TT&C time windows is determined depending on whether the task is routine or requires continuous tracking. Since some TT&C time windows may already be occupied, the available set of alternative TT&C time windows is recalculated based on the task type.

For continuous tracking tasks, which require multiple continuous and uninterrupted TT&C time windows, each time window in the set generated for the task’s continuous tracking plan (as detailed in Section 3.3) must be checked to identify which time windows remain unoccupied. The unoccupied TT&C time windows are then considered available for task allocation. For both splittable and unsplittable routine tasks, each TT&C time window generated in Section 3.3 is examined for remaining available intervals. Time windows with available intervals are included in the alternative TT&C time window set for the task. Following the task selection and identification of alternative TT&C time windows, the task allocation and constraint checking process begins.

(2) Task allocation and constraint checking

After determining the available time window set, the next step is task allocation and constraint checking. To improve computational efficiency, the time window sets for both routine and continuous tracking tasks are first sorted. This sorting follows the TT&C time window selection method described in Section 4.2.2.

Next, we sequentially check whether there exists a tracking plan that satisfies the current operational task’s time window Constraints (7)–(10), temporal constraints (17)–(19), and logical constraints (20). If task $i \in \bar{N_{a}}$ is a routine task or subtask, and the TT&C time window k of a certain TT&C station m can satisfy all conditions, then it will be assigned to the current task. Based on the earliest feasible start time principle, the task’s start time $ξ_{i}$ is set to the later of the earliest start time of the available interval in the current TT&C time window, $n e w_t_{m}^{s t a r t (k)}$ (initialized as $n e w_t_{m}^{s t a r t (k)} = t_{m}^{s t a r t (k)}$ ), and the earliest start time $r_{i k}$ of the task in TT&C time window k.

(31) $ξ_{i} = m a x {n e w_t_{m}^{s t a r t (k)}, r_{i k}}$

If task $i \in N_{b}$ is a continuous tracking task, and a continuous tracking plan $u_{i}^{f} {\in \bar{U}}_{{Arc}_{i}}$ satisfies all conditions, it will be assigned to the task, and the task’s start time is then set to $ξ_{i} = t_{u_{i}^{f}}^{s t a r t}$ .

(3) Update task and TT&C resource

Once task $i$ is assigned, it is removed from the task set $\bar{N}$ . The TT&C time windows are then updated as follows:

Algorithm 1. Task Allocation Method
$Input : N_{c u r}$ : the set of tasks to be allocated, $R_{c u r}$ : the set of TT&C time windows already used, $U_{i}$ : the set of tracking plans for the continuous tracking task $i$ to be allocated, $K^{i}$ : the set of TT&C time windows that can serve routine tasks or subtask $i$ .
Output: TT&C plan for the tasks to be allocated.
1. Sort the pending task set based on the sorting method in Section 4.2.1
2. $F o r i ϵ N_{c u r} d o$
3.	$I f i ϵ N_{b} t h e n$
4.			$F o r u ϵ U_{i} d o$
5.						$I f \forall w \in u and w \notin R_{c u r} (i . e ., t h e t i m e w i n d o w w i n u h a s n o t b e e n u s e d) t h e n$
6.							$Add u$ $to the set of candidates tracking plans for continuous tracking task i$
7.						$E n d i f$
8.			$E n d f o r$
9.	$E l s e$
10.		$F o r k ϵ K^{i} t h e n$
11.				$I f k \notin R t h e n$
12.				$Add k$ $to the set of candidates tracking plans for routine task i$
13.				$E n d i f$
14.		$E n d f o r$
15.	$E n d i f$
16. $E n d f o r$
17. $F o r i ϵ N_{c u r} d o$
18.	Ranking the tracking plans based on the selection method in Section 4.2.2.
19.	$F o r v ϵ$ the set of candidates tracking solutions for task $i d o$
20.			If v satisfying the time window, and temporal logic constraints then
21.					Set the tracking plan for task $i a s v,$ $If i$ is a routine task or subtask, set the start time $ξ_{i} = m a x {n e w_t_{m}^{s t a r t (v)}, r_{i v}}$ ; otherwise, set $ξ_{i} = t_{u_{i}^{f}}^{s t a r t}$
22.			$E n d i f$
23.	$E n d f o r$
24	$I f T a s k i h a s b e e n a s s i g n e d t h e n$
25.		$Remove task i$ from the set of pending tasks
26.		$I f i ϵ N_{b} t h e n$
27.				$Add all time windows in v$ $to R_{c u r}$
28.		$E l s e$
29.				Update the available time window interval in $v$ $to [ξ_{i} + p_{i}, t_{m}^{e n d (k)}]$
30.				$I f ξ_{i} + p_{i} = t_{m}^{e n d (k)} t h e n$
31.				$Add v$ $to R_{c u r}$
32.				$E n d i f$
33.		$E n d i f$
34.	$E l s e$
35.		Proceed to Section 4.3: partial backtracking search method (Algorithm 2)
36.	$E n d i f$
37. $E n d f o r$

For continuous tracking tasks, the TT&C time windows used in the assigned plan are removed from the set of available windows. The utilized TT&C time windows are updated, and the time windows used by the current task are added to the set of already allocated time windows.

For routine tasks, the TT&C time window is allocated based on the available time slots, following the principle of assigning the earliest feasible start time. The unused portion of the TT&C time window, denoted as $[n e w_t_{m}^{s t a r t (k)}, {n e w_t}_{m}^{e n d (k)}]$ , is then updated. The update equation is as follows:

(32) $[n e w_t_{m}^{s t a r t (k)}, {n e w_t}_{m}^{e n d (k)}] = [ξ_{i} + p_{i}, t_{m}^{e n d (k)}]$

If $ξ_{i} + p_{i} = t_{m}^{e n d (k)}$ , the corresponding time window is added to the set of already used TT&C time windows. If the allocation of task $i$ fails, the process proceeds to Section 4.3, where a partial backtracking search is employed.

4.3. Partial Backtracking Search Method

In the previous section, we introduced a heuristic method for task allocation. If a task cannot be allocated, it indicates that the remaining TT&C time windows are insufficient to meet its requirements. One potential solution is to find a suitable replacement within the tracking plan of already allocated tasks. This involves backtracking, reallocating unassigned tasks, and redistributing the replaced tasks. However, as the number of tasks and their splits increases, the task node network may expand significantly, resulting in excessive backtracking time. To address this, we proposes a partial backtracking method that maintains search quality while improving backtracking efficiency.

The partial backtracking strategy, based on the release time of the rollback task, operates as follows: Since subtasks of the same parent task share the same release-to-due TT&C time windows, a subtask may fail to be scheduled if other tasks are already occupying the time window. For unsplittable tasks, a failed allocation also affects the rollback search set for the task. In this strategy, the rollback search focuses only on the set of tasks and subtasks scheduled after the release time of the failed task, forming the partial backtracking set. A task is selected from this set to release the occupied TT&C resources. The selected task is marked for reallocation. If the reallocation succeeds, the next task in the allocation set is processed. If, after backtracking through all tasks in the partial backtracking set, the failed task cannot be scheduled, it is skipped. This partial backtracking strategy reduces infeasible search spaces by avoiding redundant searches and not rolling back all previously scheduled tasks.

As illustrated in Figure 4, tasks T1, T3, and T4 are routine tasks, while T2a and T2b are subtasks of task T2. The priorities, in descending order, are: T1 > T2a = T2b = T3 = T4. In this scenario, T1 is allocated first to TDRS East, and the remaining tasks are scheduled in order based on their execution durations and due times. As shown in Case 1, tasks T2a, T3, and T4 are allocated to TDRS West. However, the remaining TT&C time window on TDRS West cannot accommodate the execution duration of task T2b. To resolve this, a partial backtracking search is performed, considering the task set after the release time of task T2 (Case 2). This allows task T4 to be rolled back, task T2b to be allocated to TDRS West, and task T4 to be scheduled on TDRS East. If the backtracking set includes task T1, which was released before task T2, the TT&C time window and temporal constraints between T2b and T2a show that even if task T1’s TT&C time window is removed, task T2b cannot be scheduled to TDRS East.

The partial backtracking strategy follows a fundamental process, with the key steps outlined below. The pseudocode for this process is provided in Algorithm 2.

(1) Check if rollback termination criteria are satisfied

First, verify whether the partial backtracking task set $Υ$ is empty. If $Υ$ is empty, the failed task $i$ is skipped. Otherwise, for the tasks in the partial backtracking task set $Υ$ that have been allocated, backtrack through them sequentially and check if they have been assigned a TT&C time window. During this backtracking process, release the occupied resources and attempt to reallocate the task $i$ . This continues until all tasks in the partial backtracking set $Υ$ have been processed.

(2) Determine if the task has been allocated a TT&C time window

Verify whether the task selected for rollback has already been allocated a tracking plan. If the task has been assigned a TT&C time window, proceed to release the occupied resources and attempt to reallocate the task.

Algorithm 2. The Partial Backtracking Search Method
Input: $i$ : the currently unscheduled tasks, $R_{c u r} :$ the set of used TT&C time windows $, N_{c u r} :$ theset of tasks to be assigned currently
Output: The tracking plan for task $i$
1 Generate the partial backtracking task set $Υ$ based on the release time of task $i$
2 If $Υ = \emptyset$ do
3	Skip the allocation for unscheduled task $i a n d r e m o v e i$ from $N_{c u r}$
4 Else
5	While $Υ \neq \emptyset$ do
6		Select the last task $l \in Υ$ from the partial backtracking task set $Υ$
7		If task $l$ has been allocated a tracking plan then
8			Add task $l$ to $N_{c u r}$
9			If $l ϵ N_{b}$ then
10				Release all TT&C time windows occupied by the continuous tracking task $l$ from $R_{c u r}$
11			Else
12				Release routine task l’s occupation of TT&C time windows
13			End if
14			Reassign task $i$ using Algorithm 1
15			If task $i$ allocation successful then
16				Break
17			End if
18		Else
19			Remove task l from the partial backtracking task set $Υ$
20		End if
21	End while
22 End if

(3) Release and reallocation of occupied resources

Once the current task is allocated a TT&C time window, release the occupied resources. For routine tasks, backtrack to the TT&C time window currently occupied by the replacement task l. Update the status of task l to unallocated and release the corresponding time window. For example: if the execution interval $[ξ_{l}, ξ_{l} + p_{l}]$ of task l is a subset of the TT&C time window $[t_{m}^{s t a r t (k)}, t_{m}^{e n d (k)}]$ , after removing task l from the allocated plan, the remaining time window $[ξ_{l} + p_{l}, t_{m}^{e n d (k)}]$ is restored to ${[ξ}_{l}, t_{m}^{e n d (k)}]$ , as the backtracked task may not fully occupy the time window $k$ . After updating the available time windows, Algorithm 1 is re-applied to allocate TT&C tracking plans for the rollback and replacement tasks. The search is terminated when a suitable replacement position is found.

For continuous tracking tasks, during the rollback process, the TT&C time windows previously assigned to the task in the continuous tracking plan are re-integrated into the remaining TT&C time window set, allowing the task to be re-selected and reallocated.

5. Numerical Study

The proposed MILP model is solved using IBM ILOG CPLEX Optimization software (version 12.6.3), and the heuristic algorithm is implemented using Java 4.6.3. All experiments are conducted on a computer with 16 GB of RAM, an Intel Core i7-9700H processor (3.00 GHz), and the Windows 10 operating system. Computation time for all tests is measured in seconds (s).

5.1. Test Instances

Spacecraft operational task scheduling that considers constrained space–ground TT&C resources and task splitting is a new combinatorial optimization problem, and no benchmark instances exist in the literature. To verify the applicability and effectiveness of the proposed method, we created test cases based on real spacecraft task scheduling scenarios and conducted algorithm comparison experiments.

The test cases are derived from publicly available operational data of the CSS. We generated the corresponding TT&C time windows using a simulation toolbox and carried out experiments based on the constructed test tasks. The scheduling period spans one day, from 00:00:00 on 6 November 2023, to 00:00:00 on 7 November 2023. Specifically, we used the existing space-based and ground-based TT&C resources and the CSS operational phase to produce visible time windows using satellite simulation toolbox. The study includes seven ground-based TT&C stations (Jiamusi, Xiamen, Sheshan, Tianshan, Hetian, Dongfeng, and Weinan) and six relay satellites: TIANLIAN_2_01, TIANLIAN_2_02, TIANLIAN_2_03, TIANLIAN_1_03, TIANLIAN_1_04, and TIANLIAN_1_05. The CSS completes an orbit approximately every 90 min. During each orbit, ground stations periodically enter and exit the CSS line of sight, whereas relay satellites in adjacent orbital positions can maintain tracking continuity [45]. Appendixes Table A1 and Table A2 list the orbital parameters of the relay satellites and the CSS, as well as the configuration of the ground-based TT&C stations. Orbital parameters are described using Two-Line Element (TLE) sets. Each TT&C station carries an antenna capable of communicating with the CSS. Ground-based TT&C stations use S-band antennas, whereas relay satellites employ Ka/S-band relay antennas [34]. The elevation angle constraints for ground-based TT&C stations are set to minimum and maximum values of 5° and 9°, respectively, and all other parameters use the satellite simulation toolbox default settings.

To evaluate the algorithm’s performance, this study constructs test cases of varying scales, with parameters based on actual spacecraft task scheduling scenarios. Since task duration depends on the task content, it is assumed that the data injection and download tasks are routine, unsplittable tasks. The duration of these tasks is randomly selected from the range U(0.2 $\times d$ ,1 $\times d$ ), where $d$ is a fixed duration of 60 s (d = 60). It is assumed that if $p_{i} \geq 2 d$ , routine task $i$ can be split. The duration of splittable routine tasks is randomly selected from two probability distributions: U(2 $\times d$ ,5 $\times d$ ) and U(5 $\times d$ ,6 $\times d$ ). These tasks are assumed to be split according to their duration $p_{i}$ and the possible durations of their subtasks. The maximum number of splits, $q$ , is set to limit the duration of tasks after splitting in each test case. To express the duration of tasks after splitting, the following calculation method is used: the initial remaining duration is $p_{c u r_r e m a i n} = p_{i}$ . The duration of the first $q - 1$ subtasks of task $i$ is then calculated using the formula:

(33) $p_{t_{j}^{i}} = d + R \times m a x {p_{m a x} - d, 0}$

where

p_{m a x} = p_{c u r_r e m a i n}^{*} - (q - j) d, j < q

, R is a random number. After assigning the duration for a subtask, the remaining duration is updated as:

p_{c u r_r e m a i n}^{*} = p_{c u r_r e m a i n} - p_{t_{j}^{i}}

. The last split task

t_{q}^{i}

for task

i

takes the remaining duration, i.e.,

p_{t_{q}^{i}} = p_{c u r_r e m a i n}^{*}

In the benchmark case, routine tasks are assumed to be evenly distributed across three time periods: early, mid, and late in the day. The task release and due time windows are randomly selected from the following: [6 November 2023 00:00:00 to 6 November 2023 12:00:00], [6 November 2023 06:00:00 to 6 November 2023 18:00:00], and [6 November 2023 12:00:00 to 7 November 2023 00:00:00]. The overlapping duration of release and due time windows for routine tasks within the same time period ranges from 4 to 6 h. The duration of continuous tracking tasks is randomly selected from the probability distribution U(45 ×d,105 × d). The release and due intervals for these tasks are set between 3 and 6 h, evenly distributed throughout the day, from [6 November 2023 00:00:00 to 7 November 2023 00:00:00].

Next, temporal logic relationships between tasks are added:

(1) Temporal relationships between tasks: Temporal precedence relationships are defined both between routine tasks and between routine and continuous tracking tasks. First, the number of precedence relationships follows a uniform distribution U(4,10), and the number of routine tasks with time interval precedence relationships follows a uniform distribution U(2,6). Then, a weight matrix is initialized to store these temporal constraints. Task pairs $(i, j)$ are selected, and it is checked whether their release and due TT&C time windows overlap and whether a task has too many temporal constraints. If these conditions are satisfied, precedence and time interval constraints are added to the weight matrix. The earliest start time interval and the latest end time interval for tasks are randomly selected from U(0,10d) and U(40d,75d), respectively. After each constraint is added, the temporal network’s negative cycle detection algorithm is invoked to ensure conflict-free temporal constraints [46].

(2) Temporal relationships between subtasks: For routine subtasks, sequential relationships are added based on the task splitting. For example, for a split set $T_{i} = {t_{1}^{i}, t_{2}^{i}, \dots, t_{q}^{i}}$ of routine task $i$ , precedence relationships are added so that earlier tasks in the split set must strictly occur before later tasks.

(3) Logical relationships: For logical relationships, it is assumed that data injection-type routine tasks contain mutually exclusive relationships. The number of data injection-type routine tasks follows a uniform distribution U(0,4).

Finally, it is assumed that task reward values follow a uniform distribution U(1,4). Since continuous tracking tasks are more critical, their reward value is set to 4, while other routine tasks have reward values following the uniform distribution U(1,4).

Further details regarding the test dataset constructed using the aforementioned method are provided in the Data Availability Statement.

5.2. Benchmark Methods

To further compare the solution performance of the algorithm proposed in this study, we first linearize the MILP model from Section 3.4. Since the objective Function (3) contains a nonlinear term $m a x {\sum_{m \in M} \sum_{k \in K} \sum_{j \in T_{i}} x_{i j}^{m k} - c_{i} + 1, 0}$ , we introduce a integer decision variable $y_{i} \in [0, + \infty)$ , $i \in N_{a}$ , to linearize the objective function. The variable $y_{i}$ satisfies the following constraints:

(34) $\sum_{m \in M} \sum_{k \in K} \sum_{j \in T_{i}} x_{i j}^{m k} - c_{i} \geq y_{i}, \forall i \in N_{a}$

Constraint (34) represents the completion constraint for task $i$ , which, due to the range of values for $y_{i}$ , limits the successful allocation of a splittable task $i \in N_{a}$ by ensuring that all its subtasks $j \in T_{i}$ are also allocated. The objective Function (3) then becomes: $m a x \sum_{i \in N_{a}} β_{i} (\sum_{m \in M} \sum_{k \in K} \sum_{j \in T_{i}} x_{i j}^{m k} - c_{i} + 1) + \sum_{i \in N_{b}} \sum_{u \in U_{i}} β_{i} z_{i}^{u}$ . This study first uses the CPLEX solver to solve the MILP model after linear relaxation of the objective function.

Furthermore, to compare the impact of the proposed priority-based heuristic task allocation method and partial backtracking strategy on algorithm performance, we developed three comparison methods:

(1) Priority Heuristic: This method utilizes only the priority-based task allocation from Section 4.2. It is referred to as the Priority Heuristic.

(2) Basic Heuristic: This method combines the priority-based allocation from Section 4.2 with a basic backtracking strategy. Specifically, when a task or subtask cannot be initially allocated and requires rollback, the basic rollback set includes all previously scheduled tasks or subtasks. During rollback, one task is selected from this set, adjusted, and reallocated to resolve conflicts. It is referred to as the Basic Heuristic.

(3) Improved Heuristic: This method combines the priority-based allocation from Section 4.2 with the partial backtracking strategy from Section 4.3. It is referred to as the Improved Heuristic.

These heuristic methods are compared with the benchmark scheduling strategy, SHRT (Scheduling Heuristic based on Earlier Release Time), which schedules tasks based on their release time using a first-come, first-served approach.

Finally, the proposed method is compared to the classic Genetic Algorithm (GA). The process starts by initializing a population with a randomly ordered task sequence. In each generation, TT&C time windows are allocated sequentially based on the task start times, as outlined in Section 4.2.3. The constraints of TT&C time windows, task temporal logic, and non-overlapping conditions are satisfied. Multi-generation iterative evolution optimizes the solution. In each generation, fitness is evaluated, parent tasks are selected via roulette wheel selection, and crossover and mutation are applied to generate offspring. The population is updated until the maximum number of generations is reached. An Improved Genetic Algorithm (IGA) is also proposed to accelerate the basic GA. In the IGA, each TT&C time window is assigned to only one task. A task tracking plan that satisfies the constraints is allocated directly from the available TT&C time window set or a continuous tracking plan set. Once allocated, the time windows are removed from the available set. Other operations are the same as in the basic GA. This acceleration strategy helps evaluate the effectiveness of the IGA.

To balance computation time and effectiveness, the GA parameters used in this study are as follows: a population size of 20, a maximum evolution of 200 generations, a crossover probability of 0.8, and a mutation probability of 0.1. The IGA uses population sizes of 20 and 100, with maximum evolutions of 200 and 1000 generations, respectively, and the same crossover and mutation probabilities as the GA. The algorithms are abbreviated as GA(20,200), IGA(20,200), and IGA(100,1000).

5.3. Analysis of the Algorithm’s Time Complexity

The complexity of the heuristic algorithm proposed in this study is determined by the priority-based task allocation method (Algorithm 1) and the partial backtracking method (Algorithm 2). The time complexity of the algorithm is analyzed as follows. First, let the number of tasks be $n = | \bar{N} |$ . During the initial task sorting, the tasks are arranged based on their release times, which has a time complexity of $O (n \log n)$ , as shown in Figure 2.

Next, traditional backtracking algorithms typically use a depth-first search strategy, starting from the root node to explore the solution space, which includes all allocated tasks. The time complexity of such an algorithm, which searches the entire allocated task set, is $O (2^{n})$ . This backtracking strategy has a high time complexity. In this study, we reduce the search space through constraint pruning techniques by considering the release time of rollback tasks. This limits the rollback tasks and uses a partial backtracking set considering release time to determine the final task set $Υ$ for the tree search. Let $Q = | Υ |$ , in the worst case, the complexity of Algorithm 2 is $O (2^{Q})$ , where $Q \leq n$ .

Finally, based on the complexity of Algorithm 2 and the computational steps of Algorithm 1, we assume the number of candidate tracking plans for the tasks is $D = \sum_{j \in \bar{N_{a}}} | {\bar{K}}_{i} | + \sum_{j \in N_{b}} | U_{i} |$ . The time complexity of Algorithm 1 is $O (n \log n + n (D \log D + D + 2^{Q}))$ . Therefore, the overall time complexity of the heuristic algorithm, combining priority rules and partial backtracking, is $O (2 n \log n + n (D \log D + D + 2^{Q}))$ .

5.4. Experimental Results

This section presents experimental validation and analysis of the algorithm’s effectiveness, followed by a sensitivity analysis on the number of tasks, the number of space-ground TT&C stations, and the number of task splits. In this study, the maximum computation time is set to 1 h (3600 s).

5.4.1. Comparative Analysis of Algorithm Effectiveness

Based on the test case construction rules, this section assumes the use of 3 TDRSs and 3 to 5 ground-based TT&C stations. Tasks can be split into a maximum of 2 subtasks. Using these parameters, 20 test cases are constructed and tested. In Table 4, “S” represents the number of TDRSs, “G” the number of ground-based TT&C stations, “RT” the number of routine tasks, and “CT” the number of continuous tracking tasks. “RE” indicates the reward generated by the task schedule, “TW” the number of TT&C time windows used, “CPU” the computation time (in seconds), “Ave” the average computational result, and ‘-‘ indicates no result was obtained within the specified time.

As shown in Table 4a, compared to the Priority Heuristic, Basic Heuristic, and Improved Heuristic, the linear relaxation solution from CPLEX does not guarantee optimality due to the linear relaxation of the objective function and large M values in the MILP model. This results in fewer tasks being scheduled, fewer time windows being used, and the lowest overall reward. As the task scale increases, CPLEX can only solve a limited number of test cases within the prescribed time.

The Improved Heuristic outperforms the Priority Heuristic by generating task allocation plans with higher average rewards and by using fewer TT&C time windows. However, in certain cases (e.g., Instances 5 and 7), task allocation using only the Priority Heuristic still yields higher rewards, even without backtracking. This occurs because, although backtracking explores a broader solution space, replacing high-priority tasks may prevent them from fitting within the available TT&C time windows.

Compared with the Basic Heuristic, the Improved Heuristic benefits from its backtracking strategy, which enables more thorough exploration of feasible solutions. Therefore, it produces higher average task-completion rewards and uses fewer TT&C time windows. In contrast, the Basic Heuristic requires backtracking to the first scheduled task, which substantially increases computation time as the instance size grows. Moreover, expanding the backtracking set disrupts the priority-based scheduling structure. The Improved Heuristic reduces computation time while achieving higher rewards.

Table 4a,b show that, relative to the two construction-based heuristic algorithms (Priority Heuristic and SHRT), the Improved Heuristic generally produces task allocation plans with higher average rewards and fewer TT&C time windows. A further comparison of the two GAs in Table 4a,b shows that the Improved Heuristic generates schedules with equal or better average rewards in less time than GA(20,200). Although GA(20,200) uses the heuristic task allocation plan proposed in this study and similar TT&C time windows, it becomes increasingly difficult to obtain results within one hour as the task size and the number of splits increase. Some instances (e.g., Instances 19 and 20) fail to produce results within the time limit. The comparison between IGA(20,200) and IGA(100,1000) indicates that larger populations and more iterations improve performance but also raise computational cost. In contrast, the Improved Heuristic achieves rewards comparable to IGA(100,1000) while requiring less time and fewer TT&C time windows.

In the following medium- and large-scale instances, GA(20,200) no longer produces results within the specified time. Because the Improved Heuristic yields better average rewards than the Basic Heuristic, we primarily compare the Improved Heuristic with CPLEX, Priority Heuristic, SHRT, and IGA(100,1000).

5.4.2. Performance Analysis for Medium-Scale Test Cases

To evaluate the algorithm’s performance as the test case scale increases, this section assumes the use of 6 TDRSs and 5 to 7 ground-based TT&C stations, with tasks split into a maximum of 2 subtasks. The symbols used in Table 5 are consistent with those in Table 4.

As shown in Table 5, as the number of tasks and resources increases, CPLEX can solve more instances. However, compared to the Improved Heuristic, CPLEX yields lower rewards and schedules fewer tasks. In comparison with Priority Heuristic algorithm, the proposed Improved Heuristic algorithm generates scheduling solutions with higher reward values in a shorter computation time when the number of tasks and TT&C stations is large. It also saves an average of 12–13 TT&C time windows. In comparison to SHRT, the Improved Heuristic significantly improves task completion rewards and saves an average of 11–12 TT&C time windows, while SHRT provides results in an average of 5–8 s. Compared to IGA(100,1000), the Improved Heuristic still achieves higher reward values in less time, while using fewer TT&C time windows.

5.4.3. Impact of Task Splits on Algorithm Performance

To analyze the effect of task splitting on the algorithm, this section assumes tasks can be split into a maximum of 3 subtasks, extending the instances from Section 5.4.2. The space-based TT&C stations consist of 6 TDRSs, and the number of ground-based TT&C stations ranges from 5 to 7, generating 20 additional test cases (41–60) corresponding to test cases 21–40. The symbols used in Table 6 are consistent with those in Table 4.

As shown in Table 6, CPLEX finds solutions for more instances as the scale increases, but yields lower rewards compared to the Improved Heuristic. The results indicate that as the number of task splits increases, the Improved Heuristic generates scheduling solutions with higher rewards and better resource utilization in less computation time, outperforming the Priority Heuristic, SHRT, and IGA(100,1000) under the same task and TT&C station scale. In cases with more task splits, the Improved Heuristic significantly outperforms the other two algorithms.

A comparison of Table 5 and Table 6 shows that as task splits increase, the computation time for all three heuristics grows. However, the Improved Heuristic still provides results in an average of 20 s. For test cases differing only in the number of splits (e.g., test cases 21 and 41), the difference in average reward and TT&C time windows used is small. This suggests that increasing task splits does not significantly increase the total task reward but does raise scheduling complexity.

5.4.4. Performance Analysis for Larger Test Case Scales

This section evaluates the computation for larger-scale instances. Since the number of continuous tracking tasks is typically low in practice, we assume 3 to 6 continuous tracking tasks per day. The number of routine tasks ranges from 80 to 200, with each task splittable into a maximum of two subtasks. The space-based TT&C stations consist of 6 TDRSs, and the ground-based TT&C stations range from 5 to 7. The symbols used in Table 7 are consistent with those in Table 6.

The results in Table 7 show that CPLEX continues to perform poorly on large-scale instances relative to the Improved Heuristic due to the effects of the big-M values and the linear relaxation of the objective function, which lead to lower reward values. Compared with the two heuristic algorithms (Priority Heuristic and SHRT), the Improved Heuristic typically produces task allocation plans with higher average rewards and fewer TT&C time windows. Compared with IGA(100,1000), the Improved Heuristic obtains nearly the same average reward while using fewer TT&C time windows and less computation time.

5.4.5. Comparative Analysis in Complex Scenarios

This section compares medium-scale instances with varying numbers of stations (3 to 6 TDRSs and 5 to 7 ground-based TT&C stations) and differing time and temporal requirements. We generate instances of varying complexity using the method described in Section 5.1 as the basic scenario. For more complex scenarios, we define general and difficult test cases, where overlapping time windows for task release and due dates last 2–3 h and 1.5–2 h, respectively. The number of precedence constraints between tasks follows uniform distributions U(7,12) and U(10,15), while the number of precedence constraints with time intervals follows U(4,8) and U(6,10). The maximum number of task splits is assumed to be 2. The symbols used in Table 8 are consistent with those in Table 7.

The results in Table 8 show that, compared to CPLEX, the Improved Heuristic achieves higher rewards across various complexities. Compared to SHRT and Priority Heuristic, the Improved Heuristic generates higher average rewards in test cases with different complexities, with average improvements ranging from 0.43% to 11.87% over SHRT and from 0.65% to 14.29% over Priority Heuristic. When compared to IGA(100,1000), the Improved Heuristic produces schedules with similar average rewards, achieving an average task completion time of 20 s. Additionally, it reduces the number of TT&C time windows used in test cases of varying complexity, saving between 61.68% and 135.35% of TT&C time windows. In terms of computation time, IGA(100,1000) is the most time-consuming, whereas the Improved Heuristic, SHRT, and Priority Heuristic algorithms show similar runtimes.

Figure 5 compares the models and algorithms in terms of rewards and the number of TT&C time windows used. From Table 8 and Figure 5, increasing the station capacity (Arg 1 to Arg 2) in the benchmark instances yields more available TT&C time windows, enabling more tasks to be scheduled and resulting in higher rewards. When comparing the basic, general, and difficult instances with the same number of TT&C stations (Arg 2, Arg 3 and Arg 4), it can be observed that the general cases have lower rewards. This suggests that the release-to-due time duration and the number of temporal constraints affect the task’s reward value. Planners should set appropriate release-to-due time intervals and establish suitable temporal relationships between tasks for optimal scheduling results.

6. Conclusions

With the rapid development of space technology, the complexity of spacecraft mission scheduling has increased substantially. During the operational phase of complex spacecraft such as space stations, ground operations and planning departments face the growing challenge of managing a larger number of tasks, limited space- and ground-based TT&C resources, and diverse operational requirements. Efficient scheduling of spacecraft tasks and maximizing the reward of completed tasks have therefore become critical objectives.

This study examines the spacecraft task scheduling problem under constrained TT&C resources and task splitting requirements. The focus is on efficiently allocating limited TT&C resources to support splittable and unsplittable routine tasks and continuous tracking tasks. The scheduling must satisfy several constraints, including service time windows for routine tasks, TT&C requirements for continuous tracking tasks, coupling between routine and continuous tracking tasks, temporal logic dependencies, visibility constraints, and non-overlapping scheduling conditions. To address this problem, we propose a MILP model that optimizes task scheduling given these constraints and aims to maximize the nonlinear rewards associated with completed tasks.

To improve reward performance and accelerate computation, we introduce a heuristic algorithm based on priority rules and partial backtracking. The algorithm assigns priorities according to task reward, deadline, duration, and temporal relationships, enabling efficient scheduling while avoiding conflicts. When TT&C resources are insufficient, the algorithm applies a partial backtracking strategy based on task release times to enhance flexibility and improve scheduling quality.

We evaluate the proposed heuristic algorithm using experimental analysis. The results show that it produces schedules superior to those obtained by CPLEX, the priority-based heuristic, and the scheduling heuristic based on an earlier release time. Comparative experiments with the GA and IGA demonstrate that the proposed heuristic algorithm achieves similar average rewards while reducing TT&C time-window usage. Moreover, we verify its effectiveness across tasks with different numbers of splits, varying TT&C station availability, and different time requirements using test cases of multiple scales.

Future research should address additional practical challenges faced by ground operations and planning departments in task scheduling. For instance, in the context of space station task scheduling, it is crucial to recognize that certain platform activities require managing TT&C resources alongside onboard resources. This highlights the importance of task scheduling within the framework of multi-resource coupling. With the deployment of more complex spacecraft systems, such as space telescopes and multi-spacecraft systems, optimizing collaborative multi-spacecraft scheduling will be essential for improving operational efficiency and resource use.

Author Contributions

Conceptualization, J.T., J.X. and C.Q.; methodology, J.T., J.X. and C.Q.; software, J.T., Z.S. and S.W.; data curation, J.T. and Y.H.; writing—review and editing, J.T., Y.H., J.X. and C.Q. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Publicly available datasets were analyzed in this study. This data can be found here: https://doi.org/10.5281/zenodo.17721866 (accessed on 26 November 2025).

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1 Diagram of space-ground TT&C for spacecraft operational tasks.

Figure 2 Flow chart of the priority-based and partial backtracking heuristic algorithm.

Figure 3 Diagram of the impact of task’s duration and the due time on task allocation.

Figure 4 Diagram of impact of partial backtracking search on task scheduling.

Figure 5 Performance comparison of different algorithms across instance types.

Table 1

Position of our study in relation to the related works.

References	Scheduling Object						Constraints
References	SLP	SMP	SIP	LEOS	GS	TDRS	TT&C TW	O2O	O2M	CT	Dynamic	Temporal &Logical	Task Splitting
Lin et al. [14]	√
Zhu and Luo [15]	√
Zhang et al. [16]	√
Bu et al. [17]		√										√
Bu et al. [18]		√										√
Mu et al. [19]			√								√	√
Marquez et al. [20]			√									√
Karapetyan et al. [21]				√	√		√	√
Spangelo et al. [22]				√	√		√	√
Zhang et al. [23]				√	√		√	√
Chen et al. [24]				√	√		√	√
Liu et al. [25]				√	√		√	√
Fang et al. [26]				√		√	√	√
Wu et al. [27]				√		√	√	√
Hou et al. [28]				√		√	√	√
Li et al. [7]				√		√	√	√
Chen et al. [29]				√		√	√	√					√
Li et al. [30]				√		√	√	√					√
Liu et al. [31]				√		√	√	√			√		√
Deng et al. [32]				√		√	√	√			√		√
This study			√		√	√	√		√	√		√	√

SLP = Space station Long-to-medium-term stage Planning, SMP = Space station Monthly stage Planning, SIP = Space station Implementation stage Planning, LEOS = Low-to-medium Earth Orbit Satellite scheduling, GS = Ground-based TT&C station, TDRS = Tracking and Data Relay Satellites, TT&C TW = TT&C Time Window, O2O = One TT&C time window for one task, O2M = One TT&C time window for multiple tasks, CT = Continuous Tracking, √ = considered in the reference.

Table 2

Model notations.

Notation	Meaning
$M = {1, \dots, M}$	The set of TT&C stations
$K_{m} = {1, \dots, k_{m}}$	The set of TT&C time windows for station $m$ , where $m \in M$
$K = \cup_{m \in M, k \in K_{m}} [t_{m}^{s t a r t (k)}, t_{m}^{e n d (k)}]$	The entire set of TT&C time windows
$N_{a} = {1, \dots, n_{1}}$	The set of routine tasks
$N_{b} = {n_{1} + 1, \dots, n_{1} + n_{2}}$	The set of continuous tracking tasks
$N = N_{a} \cup N_{b}$	The set of all tasks from a complex spacecraft
$T_{i} = {t_{1}^{i}, t_{2}^{i}, \dots, t_{q}^{i}}$	The set of subtasks for task $i,$ where $i \in N_{a}$
$\bar{N_{a}} = \cup_{i \in N_{a}} T_{i}$	The set of routine subtasks
${\bar{N} = \bar{N_{a}} \cup N}_{b}$	The set of all pending tasks
$L = {(i, j) \| i, j \in \bar{N}}$	The set of logical relationship, indicating that task $i$ and $j$ cannot be scheduled in the same TT&C time window, where $i, j \in \bar{N}$
$E = {(i, j) \| i, j \in \bar{N}}$	The precedence constraint set, indicating that task $i$ precedes task $j$ in terms of tracking and control, where $i, j \in \bar{N}$
$G = {(i, j, g_{i j}, h_{i j}) \| i, j \in \bar{N}}$	The precedence constraint set with fixed time interval, indicating that task $i$ precedes task $j$ in tracking and control, while satisfying the earliest start time interval $g_{i j}$ and latest end time interval $h_{i j}$ , where $i, j \in \bar{N}$
$g_{i j}$	The earliest start time interval, which is the earliest time after task $i$ ends to start task $j$ , where $i, j \in \bar{N}$
$h_{i j}$	The latest end time interval, which is the latest time after task $i$ ends to complete task $j$ , where $i, j \in \bar{N}$
$c_{i}$	The number of all subtasks for task $i$ , denoted by $c_{i} = c a r d (T_{i}),$ where $i \in N$
$β_{i}$	The reward of task $i$ , where $i \in N$
$p_{i}$	The processing time of task $i$ , where $i \in \bar{N}$
$[{s t}_{i}, {e t}_{i}]$	The release and due time window of task $i$ , where $i \in \bar{N}$
${[r}_{i k}, d_{i k}]$	The available TT&C interval of task $i$ within TT&C time tindow $k$ , where $i \in \bar{N}, k \in K$
$F_{i} = {1 \dots, n_{i}}$	The number of feasible continuous tracking plans for task $i$ , where $n_{i}$ is the total number of plans, where $i \in N_{b}$
$U_{i}^{f} = {k_{1}^{f}, \dots, k_{n}^{f}}$	The $f^{t h}$ feasible continuous tracking plan for continuous tracking task $i$ , where $i \in N_{b}, k_{i}^{f} \in K$ , $f \in F_{i}$
$U_{i} = \cup_{f \in F_{i}} U_{i}^{f}$	The set of feasible tracking plans for task $i$ , where $i \in N_{b}$
$[t_{u_{i}^{f}}^{s t a r t}, t_{u_{i}^{f}}^{e n d}]$	The TT&C time window for the $f^{t h}$ feasible continuous tracking plan for continuous tracking task $i$ , where $i \in N_{b}, k_{i}^{f} \in K$ , $f \in F_{i}$
$U$ = $\cup_{i \in N_{b}, f \in F_{i}} U_{i}^{f}$	The set of all feasible continuous tracking plans

Table 3

Model Variables.

Variable	Meaning
$x_{i j}^{m k}$	Binary variable, with a value of 1 indicating the station $m$ serves the subtask $j$ of routine task $i$ in the $k^{t h}$ TT&C time window, $m \in M, k \in K, i \in N_{a}, j \in T_{i}$
$z_{i}^{u}$	Binary variable, with a value of 1 indicating the $u^{t h}$ continuous tracking plan serves the continuous tracking task $i$ , $u \in U_{i}, i \in N_{b}$
$f_{i j}^{m}$	Binary variable, with a value of 1 indicating the station $m$ serves task $j$ after serving task $i, m \in M, i, j \in \bar{N}$
$ξ_{i}$	The time to start the task $i$ , $i \in N, j \in T_{i}$

Table 4

(a) Analysis of the effectiveness of the algorithm. (b) Analysis of the effectiveness of the algorithm.

(a)
Instance	S	G	RT	CT	CPLEX			Improved Heuristic			Basic Heuristic			Priority Heuristic
Instance	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
1	3	3	10	3	19	6	1.04	30	15	2.06	32	18	3.04	27	15	0.26
2	3	3	15	3	28	7	1.01	44	17	0.34	38	21	0.97	43	19	1.59
3	3	3	20	3	19	9	1.95	51	23	0.62	39	24	2.11	46	25	0.34
4	3	3	25	3	11	6	2.28	70	28	0.34	51	30	3.34	74	32	0.38
5	3	3	30	3	-	-	-	75	28	1.04	53	40	6.09	76	32	0.41
6	3	3	35	6	36	22	4.39	95	34	0.68	95	34	58.78	94	40	0.41
7	3	3	40	6	-	-	-	109	45	0.97	78	46	58.73	112	46	0.51
8	3	3	45	6	-	-	-	124	43	6.08	107	51	142.71	107	46	3.47
9	3	3	50	6	-	-	-	125	42	8.25	81	45	384.04	126	51	4.64
10	3	3	55	6	-	-	-	118	46	5.11	114	49	203.24	116	52	0.71
Ave 1	3	3	27	4.5	-	-	-	84.1	32.1	2.55	68.8	35.8	86.31	82.1	35.8	1.27
11	3	5	10	3	10	4	0.86	31	15	0.35	29	13	0.51	31	16	0.37
12	3	5	15	3	15	7	2.18	42	17	0.48	44	16	2.13	39	18	0.58
13	3	5	20	3	-	-	-	58	23	0.56	49	33	2.34	52	23	0.44
14	3	5	25	3	-	-	-	68	24	1.22	52	32	8.72	66	30	0.63
15	3	5	30	3	16	14	4.28	75	29	5.06	75	29	15.52	69	30	0.76
16	3	5	35	6	-	-	-	97	38	1.59	97	38	17.59	92	43	0.94
17	3	5	40	6	-	-	-	91	40	2.98	85	52	137.96	95	47	1.06
18	3	5	45	6	-	-	-	104	42	6.58	100	57	109.27	104	50	1.14
19	3	5	50	6	-	-	-	116	48	2.45	105	24	252.21	116	50	1.19
20	3	5	55	6	-	-	-	119	48	3.25	73	57	52.03	114	53	1.03
Ave 2	3	5	32.5	4.5	-	-	-	80.1	32.4	2.45	70.9	35.1	59.83	77.8	36	0.81
(b)
Instance	S	G	RT	CT	SHRT			GA(20,200)			IGA(20,200)			IGA(100,1000)
Instance	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
1	3	3	10	3	24	14	0.31	30	14	137.5	26	21	0.82	24	21	11.75
2	3	3	15	3	34	16	0.47	33	15	292.18	40	29	1.63	36	26	33.94
3	3	3	20	3	52	26	0.58	47	21	488.75	49	38	1.27	49	36	31.16
4	3	3	25	3	69	29	0.45	67	31	287.04	66	41	1.19	66	40	33.76
5	3	3	30	3	78	34	0.67	76	30	550.53	76	55	2.58	76	53	36.67
6	3	3	35	6	97	41	0.42	98	39	548.24	87	62	2.16	84	61	57.62
7	3	3	40	6	112	44	0.49	113	39	653.41	102	62	2.95	101	63	72.98
8	3	3	45	6	96	46	0.52	110	45	852.38	111	63	3.47	113	68	85.67
9	3	3	50	6	127	52	0.62	121	48	1072.53	121	68	4.53	127	68	96.59
10	3	3	55	6	120	51	0.49	122	50	1245.98	123	70	4.39	126	72	93.93
Ave 1	3	3	27	4.5	80.9	35.3	0.5	81.7	33.2	612.85	80.1	50.9	2.5	80.2	50.8	55.41
11	3	5	10	3	31	16	0.31	33	13	315.54	31	17	0.94	35	18	11.99
12	3	5	15	3	42	18	0.55	43	11	770.74	44	28	1.32	43	27	46.65
13	3	5	20	3	48	19	0.41	52	19	489.25	55	35	1.35	58	37	42.9
14	3	5	25	3	66	30	0.58	66	25	821.35	65	43	2.53	67	44	35.95
15	3	5	30	3	75	30	0.66	80	29	1086.94	82	55	1.95	86	54	63.38
16	3	5	35	6	97	43	0.85	83	35	1499.78	84	65	3.56	83	66	70.89
17	3	5	40	6	92	45	0.99	102	36	1984.07	87	73	4.06	85	74	85.93
18	3	5	45	6	112	52	1.22	108	34	2273.41	94	73	4.68	93	74	109.33
19	3	5	50	6	116	53	0.72	-	-	-	135	76	4,66	131	70	100.57
20	3	5	55	6	120	58	0.86	-	-	-	143	79	4.97	141	75	112.21
Ave 2	3	5	32.5	4.5	79.9	36.4	0.72	-	-	-	82	54.4	2.54	82.2	53.9	67.98

Table 5

Analysis of test results at medium case sizes.

Instance	S	G	RT	CT	CPLEX			Improved Heuristic			Priority Heuristic			SHRT			IGA(100,1000)
Instance	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
21	6	5	30	3	-	-	-	73	26	8.25	69	34	3.94	72	34	3.41	72	52	54.41
22	6	5	35	3	79	23	15.33	84	30	15.25	83	38	4.28	74	36	4.05	78	55	68.64
23	6	5	40	3	34	19	12.95	106	35	1.81	106	43	4.91	102	41	4.86	100	68	125.55
24	6	5	45	3	53	39	14.28	97	34	12.14	94	47	6.87	91	45	4.81	91	80	112.66
25	6	5	50	3	-	-	-	119	40	10.12	113	50	5.69	114	50	5.57	112	87	161.43
26	6	5	55	6	-	-	-	151	49	11.16	150	65	6.33	147	64	6.05	140	102	179.39
27	6	5	60	6	109	47	19.48	170	62	16.34	157	70	6.89	159	70	6.68	153	110	191.54
28	6	5	65	6	105	49	25.64	168	55	18.82	165	72	7.36	168	69	6.78	159	114	209.41
29	6	5	70	6	86	51	33.52	179	56	15.76	163	75	7.58	157	71	7.65	168	115	231.09
30	6	5	75	6	109	45	36.49	188	60	20.75	185	79	8.82	184	80	8.53	172	127	236.79
Ave 1	6	5	52.5	4.5	-	-	-	133.5	44.7	13.04	128.5	57.3	6.27	126.8	56	5.84	124.5	91	157.09
31	6	7	30	3	39	31	7.54	73	30	13.58	69	36	5.64	65	36	6.74	66	56	66.89
32	6	7	35	3	74	29	8.73	99	36	7.89	98	44	4.94	94	43	5.49	96	63	188.01
33	6	7	40	3	63	26	14.32	94	31	19.56	95	41	7.89	78	42	8.65	102	76	151.43
34	6	7	45	3	68	25	11,26	119	44	8.86	115	48	6.02	108	49	5.85	119	79	157.78
35	6	7	50	3	81	48	16.98	125	40	45.14	118	55	7.35	108	51	4.38	128	92	214.01
36	6	7	55	6	87	47	27.01	142	45	15.18	135	62	9.31	124	59	9.95	131	105	243.98
37	6	7	60	6	84	44	21.87	164	57	11.68	160	69	7.68	161	70	7.38	150	103	210.87
38	6	7	65	6	94	44	32.97	169	51	16.49	165	70	10.46	166	70	10.64	157	112	253.25
39	6	7	70	6	140	42	35.07	177	58	19.81	180	79	10.42	157	74	10.16	172	118	259.16
40	6	7	75	6	116	59	41.84	187	65	29.87	175	84	10.61	181	87	11.35	170	128	279.91
Ave 2	6	7	52.5	4.5	84.6	39.5	20.63	134.9	45.7	18.81	131	58.8	8.03	124.2	58.1	8.06	129.1	93.2	202.53

Table 6

Analysis of test results when the number of task splits increases.

Instance	S	G	RT	CT	CPLEX			Improved Heuristic			Priority Heuristic			SHRT			IGA(100,1000)
Instance	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
41	6	5	30	3	-	-	-	73	26	6.97	69	34	3.92	70	34	3.8	72	63	112.65
42	6	5	35	3	56	44	118.54	84	30	7.69	78	38	4.57	73	36	4.88	79	67	126.43
43	6	5	40	3	46	35	11.95	106	34	9.59	106	43	5.21	102	41	5.07	96	77	123.87
44	6	5	45	3	53	41	21.43	96	33	14.35	92	46	7.19	88	44	7.92	89	95	239.87
45	6	5	50	3	-	-	-	119	41	10.79	110	46	6.22	112	49	6.19	108	101	230.12
46	6	5	55	6	-	-	-	151	49	14.13	147	64	6.97	147	64	7.63	132	112	244.79
47	6	5	60	6	109	52	27.86	170	61	13.57	154	71	6.34	162	72	6.08	153	118	246.98
48	6	5	65	6	105	55	37.71	168	59	17.02	167	73	7.99	171	70	8.27	157	117	252.34
49	6	5	70	6	86	61	47.98	179	57	16.26	165	73	9.15	162	72	6.18	166	119	320.91
50	6	5	75	6	109	54	45.31	185	61	22.84	185	80	10.57	184	80	9.23	172	127	312.76
Ave 1	6	5	52.5	4.5	-	-	-	133.1	45.1	13.32	127.3	56.8	6.81	127.1	56.2	6.53	122.4	99.6	221.07
51	6	7	30	3	39	39	10.33	73	30	18.16	69	36	6.58	65	36	6.74	78	62	92.48
52	6	7	35	3	54	28	10.78	99	36	11.82	98	44	5.71	94	43	6.36	99	72	155.61
53	6	7	40	3	63	36	18.32	94	31	24.58	92	42	9.31	84	41	9.05	102	88	206.95
54	6	7	45	3	68	33	15.07	119	44	11.39	113	48	6.38	108	49	6.46	119	92	124.82
55	6	7	50	3	81	47	24.23	123	41	16.42	118	56	8.85	108	51	9.08	127	104	253.14
56	6	7	55	6	86	55	37.08	139	45	16.91	132	62	10.95	126	59	9.72	122	117	255.76
57	6	7	60	6	84	47	28.19	164	57	15.59	160	66	9.68	158	66	8.51	150	114	232.24
58	6	7	65	6	93	50	48.54	169	51	21.09	164	70	12.28	166	71	12.58	153	126	273.45
59	6	7	70	6	140	49	45.88	180	58	20.87	173	78	13.09	168	73	11.82	169	126	315.74
60	6	7	75	6	116	58	62.18	187	65	33.38	172	82	13.74	181	89	13.59	170	132	356.87
Ave 2	6	7	52.5	4.5	82.4	44.2	30.06	134.7	45.8	19.02	129.1	58.4	9.66	125.8	57.8	9.39	128.9	103.3	226.71

Table 7

Analysis of test results at larger case sizes.

Instance	S	G	RT	CT	CPLEX			Improved Heuristic			Priority Heuristic			SHRT			IGA(100,1000)
Instance	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
61	6	5	80	3	113	50	51.23	191	61	19.98	186	76	9.58	190	73	9.41	191	125	350.87
62	6	5	100	3	135	49	68.74	227	61	19.88	227	86	12.34	228	87	14.07	224	123	387.95
63	6	5	120	3	179	39	89.36	268	74	24.94	264	100	12.79	266	102	12.42	285	122	421.86
64	6	5	150	3	206	72	150.69	296	84	60.63	299	110	12.72	307	111	12.94	308	126	489.34
65	6	5	200	3	267	78	405.56	369	116	671.82	355	114	13.05	351	116	15.37	355	114	736.51
Ave 1	6	5	130	3	180	57.6	153.12	270.2	79.2	159.45	266.2	97.2	12.1	268.4	97.8	12.84	272.6	122	477.31
66	6	7	80	6	111	60	65.97	168	43	25.65	176	17	17.08	168	74	17.99	163	133	317.24
67	6	7	100	6	-	-	-	231	70	31.28	230	99	15.94	233	101	15.38	222	141	378.25
68	6	7	120	6	166	48	145.16	276	59	36.98	278	94	18.25	274	97	19.54	266	137	523.91
69	6	7	150	6	-	-	-	327	83	39.11	311	116	16.93	318	118	16.74	336	140	643.56
70	6	7	200	6	-	-	-	453	94	490.67	433	123	19.65	422	127	15.71	453	133	753.24
Ave 2	6	7	130	6	-	-	-	291	69.8	124.74	285.6	89.8	17.57	283	103.4	17.07	288	136.8	523.24

Table 8

Analysis of algorithm comparison tests under complex scenarios.

Instance	Complexity	S	G	RT	CT	CPLEX			Improved Heuristic			Priority Heuristic			SHRT			IGA(100,1000)
Instance	Complexity	S	G	RT	CT	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU	RE	TW	CPU
71	Basic	3	5	30	3	-	-	-	75	29	5.06	69	30	0.76	75	30	0.66	86	54	63.38
72	Basic	3	5	35	3	-	-	-	82	29	8.19	85	37	0.94	85	39	4.81	82	63	70.58
73	Basic	3	5	40	3	50	27	5.57	90	31	12.95	83	40	4.84	85	41	4.86	84	77	83.51
74	Basic	3	5	45	3	62	35	8.35	96	37	11.85	100	49	7.19	100	48	6.78	96	84	112.57
75	Basic	3	5	50	3	-	-	-	116	44	10.25	119	49	7.37	112	51	0.72	131	66	122.45
Ave 1	Basic	3	5	40	3	-	-	-	91.8	34	9.66	91.2	41	4.22	91.4	41.8	3.57	95.8	68.8	90.5
76	Basic	6	7	30	3	39	31	7.54	73	30	13.58	69	36	5.64	65	36	6.74	76	65	63.75
77	Basic	6	7	35	3	74	29	8.73	99	36	7.89	98	44	4.94	94	43	5.49	99	75	74.18
78	Basic	6	7	40	3	63	26	14.32	94	31	19.56	95	41	7.89	78	42	8.65	102	88	87.91
79	Basic	6	7	45	3	68	25	11,26	119	44	8.86	115	48	6.02	108	49	5.85	119	95	117.43
80	Basic	6	7	50	3	81	48	16.98	125	40	45.14	118	55	7.35	108	51	4.38	123	103	126.48
Ave 2	Basic	6	7	40	3	65	31.8	9.51	102	36.2	19.01	99	44.8	6.37	90.6	44.2	6.22	103.8	85.2	93.95
81	General	6	7	30	3	34	21	3.74	74	38	4.94	61	35	1.99	64	34	1.85	74	55	71.29
82	General	6	7	35	3	37	30	4.62	78	36	6.12	66	36	1.96	76	39	2.24	80	60	71.92
83	General	6	7	40	3	48	25	5.18	107	42	4.15	99	43	2.74	99	42	2.43	107	68	89.05
84	General	6	7	45	3	69	51	6.96	122	44	5.45	94	45	2.45	96	45	2.51	124	84	154.54
85	General	6	7	50	3	63	31	8.47	116	49	5.84	106	54	2.96	103	54	3.03	117	84	110.68
Ave 3	General	6	7	40	3	50.2	31.6	5.79	99.4	41.8	5.3	85.2	42.6	2.42	87.6	42.8	2.41	100.4	70.2	99.5
86	Difficult	6	7	30	3	-	-	-	75	35	2.72	82	34	1.71	78	33	1.71	79	55	66.49
87	Difficult	6	7	35	3	43	26	4.58	87	40	5.16	82	38	2.14	72	38	2.19	98	64	78.84
88	Difficult	6	7	40	3	57	33	5.48	102	42	3.61	99	48	2.41	100	48	2.34	109	68	138.99
89	Difficult	6	7	45	3	57	32	7.06	124	47	6.33	101	49	2.04	113	53	2.69	120	74	166.15
90	Difficult	6	7	50	3	79	25	7.25	133	50	6.21	118	55	2.49	125	58	3.01	142	85	158.24
Ave 4	Difficult	6	7	40	3	-	-	-	104.2	42.8	4.81	96.4	44.8	2.16	97.6	46	2.39	109.6	69.2	121.74

Appendix A. Generation of Continuous Tracking Plans

This appendix outlines the method for calculating the available continuous tracking plans for continuous tracking tasks. The detailed computational steps are provided in pseudocode Algorithm A1. Given that the time windows of ground-based TT&C stations are typically short and constrained by the coverage of space-based TT&C stations, this study assumes that overlap in continuous tracking plans can only occur within the TT&C time windows available through TDRSs. This assumption aligns with the relevant regulations governing space and ground TT&C time windows, as well as practical application scenarios in the construction of continuous tracking plans.

Appendix B. The Configuration Data of TT&C Stations

Table A1

Ground Station Parameter Configuration.

Name	Altitude (m)	Longitude (deg)	Latitude (deg)
Jiamusi	101	130.32	46.80
Xiamen	15	118.09	24.48
Sheshan	15	121.1995	31.09
Tianshan	362	120.09	48.87
Hetian	1328	79.92	37.11
Dongfeng	359	125.53	42.68
Weinan	321	109.51	34.50

Algorithm A1. Generation of continuous tracking plans

[Image omitted. Please see PDF.]

Table A2

Relay Satellite and CSS TLE Parameter Configuration.

Name	TLE_1	TLE_2
TIANLIAN 2-01	1 44076U 19017A 23309.11993694 -.00000105 00000-0 00000-0 0 9995	2 44076 0.1152 276.7978 0001279 347.6834 259.8582 1.00273196 17075
TIANLIAN 2-02	1 50005U 21124A 23309.29150920 -.00000013 00000-0 00000-0 0 9990	2 50005 1.2570 276.5095 0002495 325.1329 78.5565 1.00270678 7044
TIANLIAN 2-03	1 53100U 22078A 23309.62449943 .00000073 00000-0 00000-0 0 9996	2 53100 1.8084 280.2122 0001211 297.5439 62.2314 1.00270047 4983
TIANLIAN 1-03	1 38730U 12040A 23306.24296881 .00000040 00000-0 00000-0 0 9996	2 38730 3.2976 85.2036 0033903 179.5155 243.0873 0.99740818 41384
TIANLIAN 1-04	1 41869U 16072A 23309.57761875 .00000035 00000-0 00000-0 0 9995	2 41869 0.1303 273.2352 0028917 238.9845 277.0886 1.00271735 25749
TIANLIAN 1-05	1 49011U 21063A 23309.10836583 .00000110 00000-0 00000-0 0 9990	2 49011 0.8847 279.2967 0003920 300.5508 240.0781 1.00272409 8499
CSS	1 48274U 21035A 23310.12386029 .00073972 00000-0 84841-3 0 9992	2 48274 41.4727 11.7702 0003423 57.1403 302.9765 15.61099867144027

© 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

An Approach for Spacecraft Operational Task Scheduling Considering Constrained Space–Ground TT&C Resources and Task Splitting

Content area

Abstract

Full text

1. Introduction

2. Literature Review

2.1. Space Station Task Planning

2.2. Satellite TT&C Task Scheduling

3. Mathematical Programming Model

3.1. Problem Description

3.2. Problem Assumption

3.3. Available TT&C Interval Calculation

3.4. Model Establishment

4. Priority-Based and Partial Backtracking Heuristic Algorithm

4.1. Algorithm Framework

4.2. Priority-Based Heuristic Task Allocation Method

4.2.1. Task Selection Methods

4.2.2. TT&C Time Window Selection Methods

4.2.3. Task Allocation Method

4.3. Partial Backtracking Search Method

5. Numerical Study

5.1. Test Instances

5.2. Benchmark Methods

5.3. Analysis of the Algorithm’s Time Complexity

5.4. Experimental Results

5.4.1. Comparative Analysis of Algorithm Effectiveness

5.4.2. Performance Analysis for Medium-Scale Test Cases

5.4.3. Impact of Task Splits on Algorithm Performance

5.4.4. Performance Analysis for Larger Test Case Scales

5.4.5. Comparative Analysis in Complex Scenarios

6. Conclusions