WorksComputer Science
FPTR: Feasibility-Preserving Transactional Refinement for Deadline-Constrained Joint Beam and Resource Allocation
Abstract
Short-interval wireless schedulers must return a complete, feasible beam-and-resource allocation before each execution deadline, and a late or invalid output gives no utility in the current control cycle. Searching longer can increase transmitted traffic, but it may also miss the deadline or leave only an infeasible intermediate solution. We propose Feasibility-Preserving Transactional Refinement (FPTR), which always keeps a validated feasible allocation, the incumbent. Each refinement stage builds a separate candidate and leaves the incumbent unchanged. A candidate replaces the incumbent only if it is complete, passes the feasibility validator before its stage cutoff, and strictly improves the objective; otherwise it is discarded. Four refinement stages use this rule: buffer-aware resource selection, compatibility-group (CG) user sharing, beam-mask rebuilding from remaining demand, and joint reassignment of two resources. On 150 fixed synthetic instances, the full pipeline (Full) raises traffic by 3.83% on average over a lightweight beam-first reference and by 1.79% over its Base constructor. In a separate suite with matched inputs, Full exceeds six independent search baselines (ALNS, tabu search, GA, simulated annealing, iterated local search, and GRASP) by 6.68-8.35%, where outputs later than 100 ms receive zero utility. All 750 Full runs in the internal suite returned feasible allocations, and none exceeded 100 ms. Separating mandatory output construction from optional refinement lets spare computation time improve the allocation without endangering the incumbent. The open-source implementation supports independent reproduction.
Introduction
In each scheduling interval, the base-station scheduler studied here must, within a 100-ms execution deadline, choose which beams to activate and which users to place on each resource. The returned allocation must be complete, satisfy all coupling constraints, and be available before the next control decision. A late output, or one that violates even a single constraint, contributes no traffic to that scheduling interval.
Trying additional beam masks, user groups, or local repairs can improve the transmitted traffic. However, every search step consumes part of the same execution window needed for validation and output. If search runs too long or leaves an infeasible intermediate state, the scheduler has no improved allocation to return. The algorithmic challenge is therefore to use spare computation time without putting the current feasible allocation at risk.
Three structural couplings make this challenge non-trivial (Figure 1). First, beam activations on different resources share one global budget. Second, finite user buffers change a resource’s marginal value after earlier assignments satisfy part of the demand. Third, compatibility-group (CG) sharing links the selected user subset to a cardinality-dependent rate penalty. Together, binary beam masks and set-valued user assignments create a search space in which one-pass construction can miss useful combinations and exhaustive search is impractical.

Figure 1. Schematic overview of one scheduling interval. Beam activation, user assignment, finite demand, and resource sharing must be resolved before the execution deadline.
FPTR follows one simple rule: never put the incumbent at risk. The framework keeps a complete feasible allocation ready to be returned while every optional stage constructs an isolated candidate without modifying the incumbent. The candidate replaces the incumbent only after it is complete, validated before its stage cutoff, and strictly better. If any test fails, the candidate is discarded and the incumbent survives unchanged. This commit-or-discard gate separates mandatory output construction from optional quality improvement. We use “transactional” only in this all-or-nothing sense: a candidate is either committed as a whole or discarded as a whole.
We make four contributions. First, we formulate deadline-constrained joint beam and resource allocation as a finite combinatorial problem whose output must remain valid while optional search continues. Second, we design FPTR, a shared commit-or-discard framework for a feasible constructor and four bounded repair stages. Third, we show that, for one resource with fixed beam masks, the best CG subset of each fixed size is obtained exactly by selecting the users with the largest marginal gains, and we establish the feasible-incumbent invariant. Fourth, we evaluate traffic, feasibility, stage acceptance, quality–time trade-offs, CG stress, and exact small-case gaps on fixed synthetic suites with published checksums.
Related Work
Joint beam and resource allocation has been studied in several settings. Multiuser OFDM work allocates subcarriers, bits, and power to minimize transmit power ([23]). For integrated terrestrial–satellite networks, hybrid beamforming and user scheduling are designed to maximize sum rate and energy efficiency ([12]), and learning-based schedulers address massive-MIMO scheduling under fairness constraints ([1]).
In multi-beam LEO systems, beam decisions are coupled with other resource choices. Online convex optimization jointly handles beam hopping, user association, subcarrier allocation, and power ([9]), while beam-pattern and timeslot design minimizes transmit power subject to traffic demand ([6]). Other studies balance load and avoid interference across multiple satellites ([28]), assign frequencies across cooperating satellites ([22]), or allocate time, frequency, and space dynamically to reduce supply–demand gaps ([21]). Beam-pattern selection and user scheduling for uneven traffic are studied in ([8]), and low-complexity interference approximations keep beam scheduling tractable as the number of beams grows ([29]).
User selection and sharing add a further layer of coupling. Representative formulations combine user grouping with beam scheduling [26], graph-based user clustering with two-stage beamforming [16], learning-based fair user scheduling designed jointly with precoding [3], or user grouping with power and beamforming in NOMA–ODDM integrated sensing and communication [18]. Interference-aware graph partitioning further treats user allocation as a weighted graph problem [11].
Service- and efficiency-oriented designs extend this line. Energy-efficient beam hopping is addressed with a two-step genetic algorithm and a greedy alternative [19], and service-aware beam hopping combines satellite-image features with deep reinforcement learning when the demand distribution is unknown [25]. Hierarchical deep reinforcement learning reduces the age of information in beam-hopping networks [24], a graph-neural-network and Lyapunov framework performs scheduling and hybrid precoding in cell-free mmWave networks [2], and a data- and model-driven successive convex approximation shortens multi-cell MIMO-OFDM allocation [27]. These works broaden the attainable service objectives and reduce solution cost. They focus, however, on the quality of the final schedule or policy and on its computational cost, and they do not specify which feasible allocation to return if a refinement step is interrupted or rejected.
In wireless scheduling, deadlines have mainly constrained data delivery. Deadline-guaranteed scheduling of time-sensitive LEO traffic [30], deadline-aware virtual queues in beam scheduling [26], and URLLC latency control under link adaptation [14] bound when packets must be served, while throughput-optimal policies with queue-stability guarantees [20] address long-run service. The deadline in this paper bounds a different event: when the solver must return a feasible allocation. Large-neighborhood search provides richer repair moves, including ruin-and-recreate operations [13]. A candidate generator alone, however, does not define which intermediate state is safe to return when the search is stopped.
FPTR addresses this execution problem. It can wrap a bounded heuristic or learned candidate generator that works in an isolated candidate state, while an independent validator and a common gate decide whether the incumbent changes. Its contribution is therefore an incumbent-preserving execution protocol for deadline-constrained allocation, rather than a universal replacement for existing search methods.
System Model and Problem Formulation
Let denote the user, resource, subband, and beam sets, with cardinalities , respectively. User has buffer , i.e., a cap on the traffic that counts toward the objective in the same units as ; a base link quality in dB; and a positive capability on beam . Resource has an explicit membership set , with ; two memberships need not be adjacent. Its inclusive span is
The scheduler chooses beam indicators and one user set per resource. The global beam budget and resource-activation constraints are
Let be disjoint CGs. A singleton is always allowed, whereas two or more users may share a resource only when they belong to the same CG:
A user appears at most once in each , but may be assigned to several resources. For , selected capability and effective link value are
Only listed subbands contribute to the numerator of (4), while a nonadjacent membership uses its full first-to-last span; for example, gives . Table 1 maps the link value , in dB, to the traffic delivered in one snapshot. The step function is a deterministic one-snapshot traffic abstraction rather than a continuous physical-layer rate law. The clipped transmitted-traffic objective is
| 0 | 8 | 24 | 90 | 120 | 162 | 222 |
Table 1. Stepwise mapping from effective link value (dB) to traffic units.
The allocation problem is the finite combinatorial program
Operationally, an output earns utility only if it is feasible and is written out (serialized) before the external deadline . Before applying the beam budget, the binary activations define masks. The budget retains of them. Each resource then chooses the empty set, a singleton, or a subset of a single CG. Buffer clipping and cardinality-dependent sharing make static user rankings unreliable across resources. We therefore use bounded refinement on full-size instances and exact optimization only for small calibration cases.
Feasibility-Preserving Transactional Refinement
FPTR keeps a complete feasible fallback and a feasible incumbent , which can be returned at any time. Each bounded operator constructs an isolated candidate without modifying and has a cumulative stage cutoff . Some operators seed their candidate from , whereas others reconstruct from stage-specific masks. An allocation is complete if all required decision fields are present, and feasible if it satisfies the constraints in § 3. Validator equals 1 when allocation passes every model constraint and 0 otherwise. Let denote the elapsed time immediately after validation returns, at the point where a commit would be considered. A candidate is timely when . Formally, FPTR is , where is the number of stages and is the objective in (6). Figure 2 summarizes the cumulative stage schedule and the incumbent-preserving return path.
Figure 2. Deadline-aware FPTR pipeline. (a) Stages use cumulative completion cutoffs under the 87-ms internal budget. (b) A candidate replaces the incumbent only after timely completion, validation, and strict improvement; otherwise the feasible incumbent is retained. Final validation and serialization use the reserved 3-ms tail.
Algorithm and Cumulative Configurations
Figure 2(b) and Algorithm 1 show the common commit-or-discard control flow, whereas Figure 2(a) reports the cumulative stage cutoffs. The empty allocation is the unconditional fallback; Base and every later stage construct isolated candidates, and the incumbent changes only through the common gate.
The entry check controls launch; the post-validation time check in the gate controls timeliness. If Base is skipped or rejected, remains; final validation restores before serialization if needed.
Algorithm 1 FPTR commit-or-discard refinement
Initialize , where is the empty complete feasible allocation.
for each stage in the order Base, Global, CG, Remask, Pair do
Record stage-entry time ; if then continue.
Construct isolated candidate without modifying . If is complete, strictly improving, and before , evaluate and record when it returns.
if passes (9) then ; otherwise discard .
end for
if or then restore .
Serialize and return .
BeamFirst is a standalone reference, whereas Base through Full are cumulative configurations (Table 2). Pair is the final stage, and Full contains all five stages: Base, Global, CG, Remask, and Pair.
| Configuration | Cumulative stage added and purpose | Cutoff (ms) |
| BeamFirst | independent aggregate-mask reference | – |
| Base | diversified-mask feasible construction | 45 |
| Global | + buffer-aware marginal selection | 60 |
| CG | + CG-focused masks and valid sharing | 70 |
| Remask | + remaining-demand masks and one-resource repair | 78 |
| Full | + two-resource ruin-and-recreate | 84 |
Table 2. Cumulative configurations and stage cutoffs for an 87-ms budget.
Base evaluates diversified beam masks and greedily assigns enabled resources using the remaining buffer of each user. Global revisits retained masks and repeatedly selects the resource–group pair with the largest clipped gain. CG adds group-weighted masks; Remask rebuilds masks from incumbent users and remaining demand, then repairs one resource; Pair (two-resource ruin-and-recreate) empties two resources and refills them in both orders.
Exact Local CG Primitive
Once the mask, the resource , the traffic retained on the other resources, and the sharing cardinality are fixed, the marginal gain of each user does not depend on which other users are selected. For an unused or emptied resource , let be the unclipped traffic that user receives from the other resources. For fixed CG and sharing cardinality , define
Here is (5) with .
Proposition 1. (Top- CG selection at fixed cardinality). For fixed , unused or emptied , retained traffic on the other resources, group , and integer , a size- subset that maximizes incremental traffic is formed by the users with the largest .
Proof. For fixed , the sharing penalty is the same for every size- subset, so the incremental traffic of is . This sum is maximized by taking the largest terms.
Including the singleton scan, one fixed-resource, fixed-mask query costs , multiplied by when all free resources are scanned.
Transactional Gating and Feasibility Invariant
Let be the feasible incumbent and an isolated candidate for stage . Candidate replaces if and only if
Here is defined above. The validator checks indices, beam budget, explicit resource memberships, activation, user cardinality, and CG compatibility. The tests may be short-circuited: an incomplete, already expired, or non-improving candidate need not invoke . Thus, entering a stage or merely completing candidate construction before is insufficient: validation must also finish before the cutoff. The four conditions exclude partial, expired, infeasible, and non-improving candidates. As noted in § 1, “transactional” refers only to this whole-candidate commit-or-discard rule.
Lemma 1. (Feasible-incumbent invariant). Assume that is feasible and validator is sound for the stated constraints. After every gate operation and immediately before serialization, incumbent is feasible.
Proof. The base case holds because is feasible. Rejection leaves the incumbent unchanged, while acceptance requires ; induction therefore preserves feasibility. Final validation retains or restores .
Runtime Budgeting and Termination Behavior
Let denote the total internal budget. The timer starts before input parsing, and ms is reserved for validation and serialization when ms. Let be the cumulative cutoffs of Table 2. Stage uses cutoff , which rescales the search window and equals at ms. At ms, the five cutoffs are 45, 60, 70, 78, and 84 ms. Entry checks prevent a stage from starting after its cutoff. The post-validation check prevents a candidate that finishes late, whether it comes from a bounded plan, a mask variant, or a reconstruction, from being committed.
Experimental Evaluation
We evaluate feasible traffic (Q1), external-baseline gains (Q1b), observed feasibility and runtime (Q2), quality–time operating points (Q3), and exact small-case gaps (Q4).
Protocol
The single-threaded C++17 scheduler (g++ 13.3, -O2) ran on Linux 6.8 and a 2.30-GHz Xeon E5-2686 v4. External wall time covered process launch through output collection. A nonzero exit code, an infeasible output, or a run longer than 100 ms received zero utility. Independent Python code reparsed every output, checked all constraints, and recomputed (6).
Table 3 gives five fixed regimes, each containing 30 consecutive seeds. The target fraction of users placed in compatibility groups ranges from 0.35 to 0.75 across regimes, and in the last regime 80% of two-membership resources have nonadjacent memberships. Each of the six configurations ran as five randomized independent processes per instance. We define and , defined when . Reported percentages first average within each regime and then weight the five regimes equally. The reported percentages therefore need not equal ratios of mean traffic. Confidence intervals use 5,000 stratified bootstrap samples with the same regime weights. W/T/L denotes the number of instances, out of 150, on which Full’s median traffic is higher (wins), equal (ties), or lower (losses) than the baseline’s median. The internal evaluation contains 8,610 process launches. We additionally ran a matched external-baseline main suite on the same 150 inputs with five repeats, an 87-ms budget, the same validator, and the same 100-ms deadline. This suite contains 6,750 launches: nine methods (BeamFirst, Base, Full, and six external baselines) × 150 instances × five repeats. The external baselines are independent implementations of adaptive large-neighborhood search (ALNS) [15], tabu search [5], a genetic algorithm (GA) [17], simulated annealing (SA) [7], iterated local search (ILS) [10], and GRASP [4], rather than reproductions of particular published solvers.
| Regime | ||||||
| Small balanced | 20 | 18 | 8 | 4 | 14 | 0.44 |
| Medium long-tail | 50 | 36 | 16 | 9 | 46 | 0.32 |
| Medium tight | 50 | 36 | 16 | 9 | 26 | 0.18 |
| Large mixed | 100 | 72 | 32 | 18 | 127 | 0.22 |
| Large nonadjacent | 100 | 72 | 32 | 18 | 92 | 0.16 |
Table 3. Fixed main regimes; each contains 30 consecutive seeds.
BeamFirst is the lightweight reference, whereas Base through Full are cumulative configurations evaluated under one model. This internal suite tests cumulative refinement behavior. The separate external suite below tests Full against independent algorithms under matched inputs, budgets, validation, and deadline accounting.
Q1: Does FPTR Yield Additional Feasible Traffic? At 87 ms, Full raised traffic by 3.83% on average over BeamFirst (95% CI 3.09–4.67%) and by 1.79% over Base (1.42–2.21%). The corresponding W/T/L counts were 127/23/0 and 111/39/0. Regime-level gains over Base were positive in all five regimes, from 0.63% to 2.68%.
Adding Global, CG, Remask, and Pair in turn increased traffic by 0.44%, 0.49%, 0.59%, and 0.25%, respectively, within Full. These four stages strictly improved the median traffic of 72, 34, 39, and 40 instances, respectively. Because each configuration inherits all earlier stages, each value is the gain of one stage given the preceding stages, not its effect in isolation.
Q1b: Does Full outperform independent external baselines? At the matched 87-ms operating point, Full led all six external baselines (Table 4). W/T/L counts use all 150 instances.
| Baseline | W/T/L | Mean rel. gain (%) | 95% CI (%) | Deadline misses (of 750 runs) |
| ALNS | 134/5/11 | 7.80 | 7.03–8.56 | 74 |
| Tabu | 139/4/7 | 7.77 | 7.01–8.52 | 18 |
| GA | 127/2/21 | 6.68 | 5.91–7.47 | 44 |
| SA | 137/4/9 | 7.90 | 7.19–8.58 | 15 |
| ILS | 137/4/9 | 8.35 | 7.53–9.13 | 41 |
| GRASP | 140/2/8 | 7.61 | 6.88–8.33 | 27 |
Table 4. Matched external-baseline comparison at ms. Quality uses five-run instance medians and regime-stratified relative gains, equally weighted across regimes; W/T/L denotes wins/ties/losses of Full.
Q2: What Feasibility and Runtime Were Observed? BeamFirst, Base, and Full had median (p50) and 95th-percentile (p95) wall times of 4.23/7.71, 15.75/22.68, and 60.28/87.29 ms, respectively. All 750 Full executions passed independent validation, none exceeded 100 ms, and the worst wall time was 92.14 ms. Across all 8,610 internal launches, every output passed independent validation and none exceeded 100 ms. All external outputs were valid, with 219 deadline misses in total.
Q3: Where Do the Quality–Time Returns Diminish? Relative to 20 ms, mean traffic gains were 1.03%, 1.60%, and 1.65% at 40, 60, and 87 ms. Going from 60 to 87 ms adds only 0.05 percentage points, so the quality curve flattens after 60 ms (Figure 3(c)). The 87-ms gain has a 95% CI of 1.24–2.14%, whereas p95 wall time rises from 20.44 to 87.31 ms. Across ten-instance CG stress sets at sizes 2, 5, 10, 15, 20, Full exceeded Base at every setting. At size 20, p95 and worst wall times were 87.50 and 92.93 ms. Because the fraction of users in CGs (coverage) co-varied with the maximum group size, this experiment measures joint stress rather than an isolated size effect.
Figure 3. Quality and runtime: (a) stage gains, (b) regime gains, (c) budget trade-off, and (d) empirical CDF of wall time; intervals are stratified 95% bootstrap estimates.
Q4: How Close Is FPTR to Exact Solutions on Small Cases? The exact suite contains eleven cases with and one larger case with , drawn from consecutive unfiltered seeds. An independent dynamic-programming (DP) reference reproduced all 12 audited optima, and Base through Full returned identical objective values on every case. Full reached the optimum on eight of the 12 cases. Over all 12 cases, the optimality gap had median 0%, mean 3.19%, and maximum 25%. External ALNS, tabu search, and GA each reached all 12 optima, whereas Full reached eight. SA, ILS, and GRASP were not run on the exact suite, so this calibration does not establish a universal ranking of methods.
Figure 4. Stress and calibration: (a) co-varying CG size and coverage and (b) exact optimality gaps on 12 cases.
Threats to Validity. Evaluation uses synthetic static snapshots, one unpinned host, and a small exact suite. The additional external main suite matches inputs, objective, the 87-ms budget, validation, and deadline accounting, but uses independent implementations rather than reproductions of particular published state-of-the-art solvers; its conclusions therefore remain bounded to this model, host, and implementation family. The CG study co-varies size with coverage, and the model omits dynamic queues, fairness, mobility, richer interference, continuous precoding, and deployment traces. Runtime observations are host-specific and do not establish hard-real-time behavior. The commit-or-discard gate protects the output only when the program terminates normally; it does not cover crashes or forced termination.
Discussion and Conclusion
FPTR provides a consistent but modest improvement over the Base constructor. Base already captures many of the easily found gains through diversified masks and buffer-aware assignment, while later stages target rarer configurations. Because Base already captures most of the easily found gains, later stages rarely accept a candidate. Even so, Full beat Base on 111 of 150 instances and was worse on none. The budget sweep shows diminishing returns after 60 ms: most of the internal gain is reached by then, while the final stages, which target rarer configurations, have less time to run.
The exact suite clarifies the scope of the transactional gate. When Base and Full return the same objective, no later candidate passed all four conditions, which does not mean that the gate failed. The maximum 25% exact gap shows that FPTR guarantees feasible-incumbent preservation and strict-improvement acceptance, but not near-optimality. On the matched 87-ms main suite, Full outperformed six independent search implementations under the same validation and deadline accounting. On the 12-case exact suite, however, external ALNS, tabu search, and GA found all optima while Full found eight, so the two results should be read together. Because these baselines are independent reference implementations, the result should not be generalized to all published solvers.
In conclusion, FPTR lets spare computation time improve the allocation while keeping a feasible allocation available at all times. Future work will study dynamic multi-slot queues, learned mask priors, and deployment traces with platform-specific timing budgets.
Acknowledgements
This work was supported in part by the Major Key Project of Pengcheng Laboratory under Grant PCL2025A12-3, in part by the National Natural Science Foundation for Young Scholars of China under Grant 62103206, and in part by the Science and Technology Planning Project of Guangdong Science and Technology Department under the Guangdong Key Laboratory of Advanced IntelliSense Technology under Grant 2019B121203006.
Code and Data Availability
Source code: GitHub repository; experimental data: dataset archive.
Additional evidence and reproducibility details are provided in Appendix § 9.
Evidence and Reproducibility Summary
This appendix summarizes execution, stability, stage acceptance, exact calibration, and artifact integrity; quality uses five-run instance medians, and counts denote separate launches.
The appendix is a companion record rather than a second results narrative. It makes the evaluation unit, crediting rule, and audit boundary explicit. Each reported quantity can therefore be traced to a process launch, a generated case, or a sealed artifact.
Reading Conventions and Statistical Units
A launch denotes one independent subprocess invocation with its own input stream, execution order, random seed, and wall-clock measurement. The validator reparses the serialized allocation and recomputes the transmitted-traffic objective. A trace-reported score is diagnostic and never replaces this independent recomputation.
For instance and method , let be the credited traffic from repeat . The quality unit used in the tables is
Relative gains are averaged within each scenario before the five scenarios receive equal weight. This prevents the largest instances from determining the summary by case size alone. A late but feasible output remains available for diagnosis, whereas its credited traffic is zero under the stated 100-ms deadline.
Execution Accounting and Configuration-Level Results
| Suite | Instances | Conditions | Repeats | Launches | Valid | Misses |
| Main | 150 | 6 | 5 | 4,500 | 4,500 | 0 |
| Budget sweep | 150 | 4 | 5 | 3,000 | 3,000 | 0 |
| CG stress | 50 | 3 | 5 | 750 | 750 | 0 |
| Exact calibration | 12 | 6 | 5 | 360 | 360 | 0 |
| Total | – | – | – | 8,610 | 8,610 | 0 |
Table A1. Formal internal launch accounting; valid outputs passed independent checks.
The internal main and budget suites reused 150 inputs but launched each condition independently; the 500-ms harness assigned zero utility to nonzero exits, illegal outputs, or wall time above 100 ms.
The four internal suites serve different purposes. The main suite measures cumulative configuration behavior. The budget sweep changes the search cap while retaining the same evaluation family. The CG stress suite increases group size and coverage together. The exact suite adds independent optimization on tiny cases alongside the heuristic runs. Their launch counts should therefore not be interpreted as four disjoint collections of inputs.
Matched External-Baseline Suite
The extended external main suite used the same 150 held-out inputs, five repeats, validator, objective, 87-ms budget, and 100-ms deadline for Full and six independent baselines: ALNS, tabu search, GA, SA, ILS, and GRASP. It contained 6,750 main-suite launches. Every output was valid; 219 external launches exceeded the deadline. The earlier budget and exact calibration remain archived under reproducibility/external_comparison_extended/ in the project repository.
The external programs share the input and output contract, objective, and validation procedure, but they do not call FPTR’s core scheduler or reuse its stage traces. Each method is compiled as an independent C++17 executable. Thus, the comparison tests independently written reference implementations under a common accounting rule, rather than claiming to reproduce every published solver in the literature.
| Baseline | W/T/L | Mean rel. gain (%) | 95% CI (%) | Main misses/750 runs |
| ALNS | 134/5/11 | 7.80 | 7.03–8.56 | 74 |
| Tabu | 139/4/7 | 7.77 | 7.01–8.52 | 18 |
| GA | 127/2/21 | 6.68 | 5.91–7.47 | 44 |
| SA | 137/4/9 | 7.90 | 7.19–8.58 | 15 |
| ILS | 137/4/9 | 8.35 | 7.53–9.13 | 41 |
| GRASP | 140/2/8 | 7.61 | 6.88–8.33 | 27 |
Table A2. Full versus six independent external baselines at the matched 87-ms main condition.
Relative gains use nonzero baseline medians: 141/150 ALNS pairs, 149/150 tabu pairs, 144/150 GA pairs, 150/150 SA pairs, 148/150 ILS pairs, and 149/150 GRASP pairs. W/T/L counts include all 150 instance medians; the machine-readable archive is reproducibility/external_comparison_v3/ in the project repository.
Full led mean instance-median traffic, with 60.28/87.29/92.14-ms p50/p95/worst time and no miss in 750 launches. Table A3 weights regimes equally and pools 750 wall times; it describes quality–runtime rather than compute-matched superiority.
| Configuration | Mean | Rel. to Base (%) | Wall p50 (ms) | Wall p95 (ms) | Worst (ms) | Misses/runs |
| BeamFirst | 13467.89 | -1.82 | 4.23 | 7.71 | 8.82 | 0/750 |
| Base | 13662.15 | +0.00 | 15.75 | 22.68 | 31.50 | 0/750 |
| Global | 13732.17 | +0.44 | 27.06 | 62.12 | 64.40 | 0/750 |
| CG | 13796.05 | +0.88 | 46.40 | 73.30 | 78.09 | 0/750 |
| Remask | 13873.17 | +1.54 | 51.44 | 81.35 | 82.85 | 0/750 |
| Full | 13898.13 | +1.79 | 60.28 | 87.29 | 92.14 | 0/750 |
Table A3. Main-set quality and wall time over 150 five-run instance medians.
Wall time includes process launch, input transfer, solver execution, and output collection. Independent Python validation is reported separately. The 87-ms value is a search budget, not a hard completion-time guarantee, so the percentiles describe the observed host and implementation rather than a platform-independent bound.
Run-Level Stability and Stage Acceptance
Across the 750 same-repeat run pairs, each Full run is compared with the Base or BeamFirst run that shares its scenario, seed, and repeat index. Full won 564 pairs, tied 186, and lost none against Base, with an unweighted mean relative gain of 1.800%; against BeamFirst it won 643, tied 107, and lost none, with a mean of 3.839%. These run-level statistics use a different unit and weighting from the instance-median, regime-weighted estimates in the main text (§ 5, Q1: 1.79% and 3.83%). The five Full runs gave identical traffic on 122 of 150 instances. The relative five-run range, defined as the maximum minus the minimum transmitted traffic divided by the instance median, had a 95th percentile of 4.969% and a maximum of 7.592% across instances.
The repeated-process comparison and the stage-acceptance trace answer different questions. Repeated processes quantify outcome stability under ordinary scheduling noise. The trace records the fixed order Base–Global–CG–Remask–Pair inside one Full run, so each acceptance count is conditional on the incumbent produced by earlier stages.
Overall instance/run acceptance was 48.0/48.0% (Global), 22.7/23.3% (CG), 26.0/26.0% (Remask), and 26.7/26.7% (Pair). A 0/0 denotes no strict improvement because of a tie, expiry, or validation failure; counts are fixed-order conditional increments.
These percentages are not standalone module success rates. A later stage may have few accepted candidates because earlier stages already removed the corresponding residual structure, because the remaining budget is short, or because the candidate fails the common gate. The cumulative Full score can still improve when accepted changes are sparse, provided that each accepted change is feasible and strictly better.
| Scenario | Global | CG | Remask | Pair | |
| small-balanced | 30/150 | 2/10 | 8/40 | 5/25 | 3/15 |
| medium-longtail | 30/150 | 18/90 | 11/55 | 17/85 | 23/115 |
| medium-tight | 30/150 | 7/35 | 3/15 | 17/85 | 14/70 |
| large-mixed | 30/150 | 27/135 | 10/49 | 0/0 | 0/0 |
| large-nonadjacent | 30/150 | 18/90 | 2/16 | 0/0 | 0/0 |
| Overall | 150/750 | 72/360 | 34/175 | 39/195 | 40/200 |
Table A4. Fixed-order stage acceptance by scenario (instances/runs).
Exact Calibration and Independent Audit
| Case | BF | Base | Full | Gap | Case | BF | Base | Full | Gap | ||
| W01 | 920 | 690 | 690 | 690 | 25.00 | C07 | 449 | 449 | 449 | 449 | 0.00 |
| C02 | 237 | 237 | 237 | 237 | 0.00 | C08 | 806 | 672 | 776 | 776 | 3.72 |
| C03 | 548 | 548 | 548 | 548 | 0.00 | C09 | 804 | 528 | 744 | 744 | 7.46 |
| C04 | 1188 | 908 | 1188 | 1188 | 0.00 | C10 | 1665 | 1589 | 1631 | 1631 | 2.04 |
| C05 | 564 | 564 | 564 | 564 | 0.00 | C11 | 888 | 888 | 888 | 888 | 0.00 |
| C06 | 648 | 648 | 648 | 648 | 0.00 | C12 | 888 | 888 | 888 | 888 | 0.00 |
Table A5. Exact calibration; BF=BeamFirst; W01/C02–C12=seeds 20281001–20281012.
Independent DP reproduced all 12 sealed optima without the formal solver: 390,814 attempted transitions became 332,585 pre-prune states after 58,229 duplicate collapses; dominance removed 219,088, leaving 113,497. Layer and aggregate identities held; this suite calibrates only small-case quality.
For each enumerated beam-mask plan, the audit dynamic program carries a vector of accumulated per-user traffic after every resource layer. It enumerates the empty choice and legal compatibility-group choices, clips each vector by user buffers, and removes componentwise dominated states. This construction is independent of the heuristic implementation and explains why the audited optimum is a useful calibration target rather than a second heuristic baseline.
Budget, CG Stress, and Artifact Integrity
At 20/40/60/87 ms, gains over 20 ms were 0.00/1.03/1.60/1.65%, with p95 times 20.44/40.34/60.39/87.31 ms; all 750 launches per budget met 100 ms, and the 87-ms suite was separate. For CG maxima 2/5/10/15/20, coverage and Full–Base gain co-varied from 6.7%/0.11% to 66.7%/1.81% (intermediate gains: 0.75/3.23/2.56%); size 20 gave 87.50/92.93-ms p95/worst time and 0/50 misses.
SHA-256 manifests bind 14 sealed-result, 16 exact-audit (12 reconstructed-input), and 21 evidence files. Hash-reconstructed inputs make only the optimizer’s path independent; causal cumulative ablation is a checksum-preserved fixed-order trace.
The integrity chain is layered. Case hashes bind generated inputs, source hashes bind the generator and validator versions, and directory checksums bind the derived result files. A regenerated archive is therefore auditable at both the numerical and provenance levels. The appendix does not treat retained binaries as evidence; the documented build commands and compiler flags are the reproducible boundary.
References
- [1]Qing An, Santiago Segarra, Chris Dick, Ashutosh Sabharwal, and Rahman Doost-Mohammady. A deep reinforcement learning-based resource scheduler for massive MIMO networks. IEEE Trans. Mach. Learn. Commun. Netw., 1:242–257, 2023. doi: 10.1109/TMLCN.2023.3313988.DOI
- [2]Jiang Chang. Dynamic edge-user scheduling and hybrid precoding for cell-free mmWave MIMO networks. In Proc. IEEE WCNC, pp. 1–6, 2026. doi: 10.1109/WCNC65185.2026.11555633.DOI
- [3]Jiang Chang, Shihao Zhu, Ming Zhao, Shuangfeng Han, and Xiaoyun Wang. Distributed joint design of fairness scheduling and beamforming in user-dense cell-free networks. In Proc. IEEE VTC-Spring, pp. 1–6, 2025. doi: 10.1109/VTC2025-SPRING65109.2025.11174798.DOI
- [4]Thomas A. Feo and Mauricio G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109–133, 1995. doi: 10.1007/BF01096763.DOI
- [5]Fred Glover. Tabu search—part i. ORSA Journal on Computing, 1(3):190–206, 1989. doi: 10.1287/ijoc.1.3.190.DOI
- [6]Donghyeon Kim, Haejoon Jung, and In-Ho Lee. Adaptive beam pattern and resource allocation for multi-beam LEO satellite systems. In Proc. IEEE ICC, pp. 940–945, 2025. doi: 10.1109/ICC52391.2025.11162055.DOI
- [7]S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. doi: 10.1126/science.220.4598.671.DOI
- [8]Lei Lei, Anyue Wang, Eva Lagunas, Xin Hu, Zhengquan Zhang, Zhiqiang Wei, and Symeon Chatzinotas. Spatial–temporal resource optimization for uneven-traffic LEO satellite systems: Beam pattern selection and user scheduling. IEEE J. Sel. Areas Commun., 42(5):1279–1291, 2024. doi: 10.1109/JSAC.2024.3383445.
- [9]Chengchao Liang, Qi Zhang, Jinhong Li, Hong Yang, and Zhanjun Liu. An online convex optimization-based joint beam hopping and resource allocation scheme for LEO satellite networks. In Proc. IEEE INFOCOM Workshops, pp. 1–6, 2025. doi: 10.1109/INFOCOMWKSHPS65812.2025.11153021.DOI
- [10]Helena R. Lourenço, Olivier C. Martin, and Thomas Stützle. Iterated local search. In Fred Glover and Gary A. Kochenberger (eds.), Handbook of Metaheuristics, pp. 320–353. Kluwer Academic Publishers, Boston, MA, 2003. doi: 10.1007/0-306-48056-5_11.
- [11]Xingyu Lu, Chen Sun, and Xiqi Gao. Dynamic weighted graph partitioning for resource allocation in massive MIMO LEO satellite communication. In Proc. IEEE ICC, pp. 1–6, 2026. doi: 10.1109/ICC59461.2026.11587784.DOI
- [12]Deyi Peng, Ashok Bandi, Yun Li, Symeon Chatzinotas, and Björn Ottersten. Hybrid beamforming, user scheduling, and resource allocation for integrated terrestrial–satellite communication. IEEE Trans. Veh. Technol., 70(9):8868–8882, 2021. doi: 10.1109/TVT.2021.3097149.DOI
- [13]David Pisinger and Stefan Ropke. Large neighborhood search. In Michel Gendreau and Jean-Yves Potvin (eds.), Handbook of Metaheuristics, pp. 99–127. Springer, 3rd edition, 2019. doi: 10.1007/978-3-319-91086-4_4.DOI
- [14]Guillermo Pocovi, Klaus I. Pedersen, and Preben Mogensen. Joint link adaptation and scheduling for 5G ultra-reliable low-latency communications. IEEE Access, 6:28912–28922, 2018. doi: 10.1109/ACCESS.2018.2838585.DOI
- [15]Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4):455–472, 2006. doi: 10.1287/trsc.1050.0135.DOI
- [16]Xinting Song, Chen Liu, Yunchao Song, Huibin Liang, and Lv Ye. Joint user scheduling and two stage beamforming for LEO satellite networks. In Proc. IEEE ICICN, pp. 126–131, 2024. doi: 10.1109/ICICN62625.2024.10761357.DOI
- [17]M. Srinivas and Lalit M. Patnaik. Genetic algorithms: A survey. Computer, 27(6):17–26, 1994. doi: 10.1109/2.294849.DOI
- [18]Salma Sultana, Shuhao Zeng, Ahmed Abdelhadi, Husheng Li, Zhu Han, and H. Vincent Poor. Joint beamforming, power allocation, and user grouping for NOMA-ODDM enabled ISAC systems. In Proc. IEEE GLOBECOM, pp. 6328–6333, 2025. doi: 10.1109/GLOBECOM59602.2025.11432419.
- [19]Pradnya Taksande, Shubham Kumar Raj, and Prasanna Chaporkar. Sustainable beam hopping and resource allocation for guaranteed QoS in multi-beam LEO satellite. In Proc. IEEE COMSNETS, pp. 297–304, 2026. doi: 10.1109/COMSNETS67989.2026.11418189.
- [20]Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control, 37(12):1936–1948, 1992. doi: 10.1109/9.182479.
- [21]Jiang Tian, Jiangtao Luo, Yongyi Ran, and Ruili Zhao. Joint optimization of satellite beam hopping scheduling and time-frequency-space resource allocation under dynamic service demands. In Proc. IEEE/CIC ICCC, pp. 242–247, 2024. doi: 10.1109/ICCC62479.2024.10681784.
- [22]Guanhua Wang, Fang Yang, Jian Song, and Zhu Han. Multi-satellite beam hopping and frequency allocation for satellite-terrestrial communications. In Proc. IEEE GLOBECOM, pp. 5174–5179, 2024. doi: 10.1109/GLOBECOM52923.2024.10901533.
- [23]Cheong Yui Wong, Roger S. Cheng, Khaled Ben Letaief, and Ross D. Murch. Multiuser OFDM with adaptive subcarrier, bit, and power allocation. IEEE J. Sel. Areas Commun., 17(10):1747–1758, 1999. doi: 10.1109/49.793310.
- [24]Xia Xie, Bowen Feng, Zhang Chen, Lirong An, and Qinyu Zhang. AoI-aware scheduling and resource control via hierarchical DRL in beam hopping LEO satellite. In Proc. IEEE VTC-Fall, pp. 1–6, 2025. doi: 10.1109/VTC2025-FALL65116.2025.11310558.
- [25]Ruiyang Xu, Haoye Chai, Qingge Ma, and Mugen Peng. Service-aware adaptive beam-hopping scheduling for low earth orbit satellite networks. In Proc. IEEE WCNC Workshops, pp. 1–6, 2026. doi: 10.1109/WCNCW67598.2026.11555219.
- [26]Wencong Xu, Zhongliang Deng, Lu Yin, Haitao Yu, Zhizhong Wang, and Zhuoyan Liu. Resource allocation for LEO satellites with joint user grouping and beam scheduling. In Proc. IEEE IC MTAE, pp. 536–542, 2025. doi: 10.1109/ICMTAE6890.2025.11427856.
- [27]Leyu Zhao, Fangming Zou, and Ying Cui. UPSCA-SR: Fast joint optimal resource allocation for multi-cell MIMO-OFDM networks. In Proc. IEEE ICC, pp. 1–6, 2026a. doi: 10.1109/ICC59461.2026.11588035.
- [28]Ruili Zhao, Jun Cai, Jiangtao Luo, Yongyi Ran, Junpeng Gao, and Yifan Xu. Joint beam hopping and resource allocation for load balancing and interference avoidance in multi-LEO satellite networks. In Proc. IEEE ICC, pp. 958–963, 2025. doi: 10.1109/ICC52391.2025.11161887.
- [29]Xiaohui Zhao, Zhanwei Yu, Lei You, Lei Lei, and Di Yuan. Massive beam scheduling in LEO systems: Low complexity via effective interference approximation. In Proc. IEEE WCNC, pp. 1–6, 2026b. doi: 10.1109/WCNC65185.2026.1155755.
- [30]Ling Zheng, Guodong Wei, Qianxi Men, Yingge Feng, and Weitao Pan. Deadline guaranteed scheduling based on time-ordered queues for time-sensitive low-earth-orbit satellite networks. In Proc. IEEE VTC-Fall, pp. 1–6, 2025. doi: 10.1109/VTC2025-Fall65116.2025.11310318.


