betaFeedback

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.

Schematic overview showing a multi-beam transmitter with beam activation, user assignment, finite demand, resource sharing, and resource–subband coupling

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 U,R,T,P\mathcal{U},\mathcal{R},\mathcal{T},\mathcal{P} denote the user, resource, subband, and beam sets, with cardinalities N,K,T,PN,K,T,P, respectively. User uu has buffer 1≤Bu≤10,0001 \le B_u \le10{,}000, i.e., a cap on the traffic that counts toward the objective in the same units as q(z)q(z); a base link quality γu\gamma_u in dB; and a positive capability cu,pc_{u,p} on beam pp. Resource rr has an explicit membership set Tr⊆T\mathcal{T}_r \subseteq\mathcal{T}, with ∣Tr∣∈{1,2}\lvert\mathcal{T}_r\rvert\in\{1,2\}; two memberships need not be adjacent. Its inclusive span is

dr=max⁡Tr−min⁡Tr+1.(1)d_r = \max\mathcal{T}_r - \min\mathcal{T}_r + 1. \tag*{(1)}

The scheduler chooses beam indicators αt,p∈{0,1}\alpha_{t,p} \in\{0,1\} and one user set GrG_r per resource. The global beam budget and resource-activation constraints are

∑t∈T∑p∈Pαt,p≤L,Gr≠∅⇒∑p∈Pαt,p≥1, ∀t∈Tr.(2)\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{P}} \alpha_{t,p} \le L,\qquad G_r \ne\varnothing\Rightarrow\sum_{p\in\mathcal{P}}\alpha_{t,p} \ge1,\ \forall t\in\mathcal{T}_r. \tag*{(2)}

Let C1,…,CM\mathcal{C}_1,\ldots,\mathcal{C}_M 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:

Gr∈{∅}∪{{u}:u∈U}∪⋃m=1M{G:G⊆Cm, ∣G∣≥2}.(3)G_r \in\{\varnothing\}\cup\{\{u\}:u\in\mathcal{U}\}\cup\bigcup_{m=1}^{M}\{G:G\subseteq\mathcal{C}_m,\ \lvert G\rvert\ge2\}. \tag*{(3)}

A user appears at most once in each GrG_r, but may be assigned to several resources. For u∈Gru \in G_r, selected capability and effective link value are

cˉu,r(α)=∑t∈Tr∑p∈Pcu,pαt,pdr,(4)\bar{c}_{u,r}(\alpha)=\frac{\sum_{t\in T_r}\sum_{p\in P}c_{u,p}\alpha_{t,p}}{d_r}, \tag*{(4)}
zu,r=γu+10log⁡101∣Gr∣+10log⁡10cˉu,r(α)∑p∈Pcu,p.(5)z_{u,r}=\gamma_u+10\log_{10}\frac{1}{\lvert G_r\rvert}+10\log_{10}\frac{\bar{c}_{u,r}(\alpha)}{\sum_{p\in P}c_{u,p}}. \tag*{(5)}

Only listed subbands contribute to the numerator of (4), while a nonadjacent membership uses its full first-to-last span; for example, Tr={2,5}T_r=\{2,5\} gives dr=4d_r=4. Table 1 maps the link value zz, in dB, to the traffic q(z)q(z) 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

zz(−∞,−10](-\infty,-10](−10,0](-10,0](0,3](0,3](3,10](3,10](10,15](10,15](15,20](15,20](20,∞)(20,\infty)
q(z)q(z)082490120162222

Table 1. Stepwise mapping from effective link value (dB) to traffic units.

F(α,G)=∑u∈Umin⁡{Bu,∑r:u∈Grq(zu,r)}.(6)F(\alpha,G)=\sum_{u\in\mathcal{U}}\min\left\{B_u,\sum_{r:u\in G_r}q(z_{u,r})\right\}. \tag*{(6)}

The allocation problem is the finite combinatorial program

max⁡α,GF(α,G)s.t.(2), (3),αt,p∈{0,1} ∀(t,p).(7)\begin{aligned} \max_{\alpha,G}\quad&F(\alpha,G)\\ \text{s.t.}\quad&(2),\ (3),\qquad\alpha_{t,p}\in\{0,1\}\ \forall(t,p). \tag*{(7)} \end{aligned}

Operationally, an output earns utility only if it is feasible and is written out (serialized) before the external deadline DD. Before applying the beam budget, the PTPT binary activations define 2PT2^{PT} masks. The budget retains ∑ℓ=0L(PTℓ)\sum_{\ell=0}^{L}\binom{PT}{\ell} 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 I0I_0 and a feasible incumbent II, which can be returned at any time. Each bounded operator RjR_j constructs an isolated candidate CC without modifying II and has a cumulative stage cutoff tjt_j. Some operators seed their candidate from II, whereas others reconstruct CC 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 V(A)V(A) equals 1 when allocation AA passes every model constraint and 0 otherwise. Let τdone(C)\tau_{\mathrm{done}}(C) denote the elapsed time immediately after validation returns, at the point where a commit would be considered. A candidate is timely when τdone(C)<tj\tau_{\mathrm{done}}(C)<t_j. Formally, FPTR is (I0,{Rj,tj}j=1J,V,F)(I_0,\{R_j,t_j\}_{j=1}^{J},V,F), where J=5J=5 is the number of stages and FF 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, I0I_0 remains; final validation restores I0I_0 before serialization if needed.

Algorithm 1 FPTR commit-or-discard refinement

  1. Initialize I←I0I \leftarrow I_0, where I0I_0 is the empty complete feasible allocation.

  2. for each stage jj in the order Base, Global, CG, Remask, Pair do

  3. Record stage-entry time τin\tau_{\mathrm{in}}; if τin≥tj\tau_{\mathrm{in}} \ge t_j then continue.

  4. Construct isolated candidate C←Rj(I)C \leftarrow\mathcal{R}_j(I) without modifying II. If CC is complete, strictly improving, and before tjt_j, evaluate V(C)V(C) and record τdone(C)\tau_{\mathrm{done}}(C) when it returns.

  5. if CC passes (9) then I←CI \leftarrow C; otherwise discard CC.

  6. end for

  7. if ¬complete⁡(I)\neg\operatorname{complete}(I) or V(I)=0V(I)=0 then restore I←I0I \leftarrow I_0.

  8. Serialize and return II.

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.

ConfigurationCumulative stage added and purposeCutoff (ms)
BeamFirstindependent aggregate-mask reference–
Basediversified-mask feasible construction45
Global+ buffer-aware marginal selection60
CG+ CG-focused masks and valid sharing70
Remask+ remaining-demand masks and one-resource repair78
Full+ two-resource ruin-and-recreate84

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 rr, the traffic retained on the other resources, and the sharing cardinality ss are fixed, the marginal gain of each user does not depend on which other users are selected. For an unused or emptied resource rr, let Yu=∑k≠r:u∈Gkq(zu,k)Y_u=\sum_{k\ne r:u\in G_k}q(z_{u,k}) be the unclipped traffic that user uu receives from the other resources. For fixed CG CmC_m and sharing cardinality ss, define

δu,r(s)=min⁡{Bu,Yu+q(zu,r(s))}−min⁡{Bu,Yu}.(8)\delta_{u,r}^{(s)}=\min\{B_u,Y_u+q(z_{u,r}^{(s)})\}-\min\{B_u,Y_u\}. \tag*{(8)}

Here zu,r(s)z_{u,r}^{(s)} is (5) with ∣Gr∣=s\lvert G_r\rvert=s.

Proposition 1. (Top-ss CG selection at fixed cardinality). For fixed α\alpha, unused or emptied rr, retained traffic YY on the other resources, group CmC_m, and integer 2≤s≤∣Cm∣2 \le s \le|C_m|, a size-ss subset that maximizes incremental traffic is formed by the ss users with the largest δu,r(s)\delta_{u,r}^{(s)}.

Proof. For fixed ss, the sharing penalty is the same for every size-ss subset, so the incremental traffic of SS is ∑u∈Sδu,r(s)\sum_{u \in S}\delta_{u,r}^{(s)}. This sum is maximized by taking the ss largest terms.

Including the singleton scan, one fixed-resource, fixed-mask query costs O(N+∑mgm2log⁡gm)O(N + \sum_m g_m^2 \log g_m), multiplied by KfreeK_{\mathrm{free}} when all free resources are scanned.

Transactional Gating and Feasibility Invariant

Let II be the feasible incumbent and CC an isolated candidate for stage jj. Candidate CC replaces II if and only if

complete⁡(C)∧τdone(C)<tj∧V(C)=1∧F(C)>F(I).(9)\operatorname{complete}(C) \land\tau_{\mathrm{done}}(C) < t_j \land V(C) = 1 \land F(C) > F(I). \tag*{(9)}

Here τdone(C)\tau_{\mathrm{done}}(C) 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 VV. Thus, entering a stage or merely completing candidate construction before tjt_j 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 I0I_0 is feasible and validator VV is sound for the stated constraints. After every gate operation and immediately before serialization, incumbent II is feasible.

Proof. The base case holds because I0I_0 is feasible. Rejection leaves the incumbent unchanged, while acceptance requires V(C)=1V(C) = 1; induction therefore preserves feasibility. Final validation retains II or restores I0I_0.

Runtime Budgeting and Termination Behavior

Let Γ\Gamma denote the total internal budget. The timer starts before input parsing, and τtail=3\tau_{\mathrm{tail}} = 3 ms is reserved for validation and serialization when Γ≥20\Gamma\ge20 ms. Let ρ=(45,60,70,78,84)\rho= (45, 60, 70, 78, 84) be the cumulative cutoffs of Table 2. Stage jj uses cutoff tj=(Γ−τtail)ρj/84t_j = (\Gamma- \tau_{\mathrm{tail}})\rho_j/84, which rescales the search window Γ−τtail\Gamma- \tau_{\mathrm{tail}} and equals ρj\rho_j at Γ=87\Gamma= 87 ms. At Γ=87\Gamma= 87 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 F~i,m=median⁡j=15Fi,m,j\tilde{F}_{i,m} = \operatorname{median}_{j=1}^{5} F_{i,m,j} and gi(A,B)=(F~i,A−F~i,B)/F~i,Bg_i(A,B) = (\tilde{F}_{i,A} - \tilde{F}_{i,B})/\tilde{F}_{i,B}, defined when F~i,B>0\tilde{F}_{i,B} > 0. Reported percentages first average gig_i 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.

RegimeNNKKPPTTLLL/(PT)L/(PT)
Small balanced201884140.44
Medium long-tail5036169460.32
Medium tight5036169260.18
Large mixed1007232181270.22
Large nonadjacent100723218920.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.

BaselineW/T/LMean rel. gain (%)95% CI (%)Deadline misses (of 750 runs)
ALNS134/5/117.807.03–8.5674
Tabu139/4/77.777.01–8.5218
GA127/2/216.685.91–7.4744
SA137/4/97.907.19–8.5815
ILS137/4/98.357.53–9.1341
GRASP140/2/87.616.88–8.3327

Table 4. Matched external-baseline comparison at Γ=87\Gamma= 87 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 (N,K,P,T)=(5,4,4,3)(N, K, P, T) = (5, 4, 4, 3) and one larger case with (N,K,P,T)=(8,8,6,4)(N, K, P, T) = (8, 8, 6, 4), 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 (OPT−F)/OPT(\mathrm{OPT} - F)/\mathrm{OPT} 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 ii and method mm, let Fi,m,jF_{i,m,j} be the credited traffic from repeat jj. The quality unit used in the tables is

F~i,m=median⁡j=1,…,5Fi,m,j,gi(A,B)=F~i,A−F~i,BF~i,B.(10)\widetilde{F}_{i,m} = \operatorname{median}_{j=1,\ldots,5} F_{i,m,j}, \qquad g_i(A,B) = \frac{\widetilde{F}_{i,A}-\widetilde{F}_{i,B}}{\widetilde{F}_{i,B}}. \tag*{(10)}

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

SuiteInstancesConditionsRepeatsLaunchesValidMisses
Main150654,5004,5000
Budget sweep150453,0003,0000
CG stress50357507500
Exact calibration12653603600
Total–––8,6108,6100

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.

BaselineW/T/LMean rel. gain (%)95% CI (%)Main misses/750 runs
ALNS134/5/117.807.03–8.5674
Tabu139/4/77.777.01–8.5218
GA127/2/216.685.91–7.4744
SA137/4/97.907.19–8.5815
ILS137/4/98.357.53–9.1341
GRASP140/2/87.616.88–8.3327

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.

ConfigurationMean Fˉ\bar{F}Rel. to Base (%)Wall p50 (ms)Wall p95 (ms)Worst (ms)Misses/runs
BeamFirst13467.89-1.824.237.718.820/750
Base13662.15+0.0015.7522.6831.500/750
Global13732.17+0.4427.0662.1264.400/750
CG13796.05+0.8846.4073.3078.090/750
Remask13873.17+1.5451.4481.3582.850/750
Full13898.13+1.7960.2887.2992.140/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.

Scenarion/5nn/5nGlobalCGRemaskPair
small-balanced30/1502/108/405/253/15
medium-longtail30/15018/9011/5517/8523/115
medium-tight30/1507/353/1517/8514/70
large-mixed30/15027/13510/490/00/0
large-nonadjacent30/15018/902/160/00/0
Overall150/75072/36034/17539/19540/200

Table A4. Fixed-order stage acceptance by scenario (instances/runs).

Exact Calibration and Independent Audit

CaseF⋆F^\starBFBaseFullGapCaseF⋆F^\starBFBaseFullGap
W0192069069069025.00C074494494494490.00
C022372372372370.00C088066727767763.72
C035485485485480.00C098045287447447.46
C041188908118811880.00C1016651589163116312.04
C055645645645640.00C118888888888880.00
C066486486486480.00C128888888888880.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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [17]M. Srinivas and Lalit M. Patnaik. Genetic algorithms: A survey. Computer, 27(6):17–26, 1994. doi: 10.1109/2.294849.DOI
  18. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_zuv9w567
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents