FPTR: Feasibility-Preserving Transactional Refinement for Deadline-Constrained Joint Beam and Resource Allocation

Preprint

FPTR: F EASIBILITY-P RESERVING T RANSACTIONAL R EFINEMENT FOR D EADLINE -C ONSTRAINED J OINT B EAM AND R ESOURCE A LLOCATION Minghao Kong1,2∗ Zirong Liu1,∗ Jianhao Wu1 Muyao Chen1 Jianxin Wu2† Rongjie Wang1,†

arXiv:2611.06491v1 [cs.AI] 4 Nov 2026

1

Department of Network Intelligence, Pengcheng Laboratory Shenzhen, China 2 School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen Campus, Shenzhen, China wangrj@pcl.ac.cn, wujx65@mail.sysu.edu.cn

A BSTRACT Short-interval wireless schedulers must return a complete, feasible beam-andresource 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.

1

I NTRODUCTION

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. ∗ †

Minghao Kong and Zirong Liu contributed equally to this work. Corresponding authors: Jianxin Wu and Rongjie Wang.

1

Preprint

(b) Resource and subband coupling

(a) Scheduling snapshot

Resources r1 – r6

Multi-beam transmitter

CG1

Buffer Bu

u1

p2

p3

p4 Subbands t1 – t6

p1

r1

CG2

u2

u3

u5

u4

u6 Nearly full

Shared

Shared

Dedicated

Dedicated

r2

t1

p1

t2

p2

r3

r4

r5

r6

Single membership Dual membership

p3

t3

Nonadjacent membership

p1

t4 t5

p4

t6

p2

Inclusive span

(b) Resource (b) Resource and subband and subband coupling coupling

(a) Scheduling (a) Scheduling snapshot snapshot

r –r r –r Figure 1: Schematic overview of one scheduling interval. Beam activation, Resources userResources assignment, finite Multi-beam Multi-beam transmitter transmitter r rr rr rr rr rr r demand, and resource sharing must be resolved before the execution deadline. Single Single 1

p1

p1 p

2

pp2 3

p3 p4

p4

6

43

1

6

1

21

32

54

t1

t1

p1

p1

65

6

membership membership

t2

t2

p2

p2

Dual

Dual

12

2

3

3 4

4

5

5

6

6

3

4

5

Shared Shared

Shared Shared

Dedicated Dedicated Dedicated Dedicated

6

Subbands t1 – t6

1

Subbands t1 – t6

membership Three structural couplings make this challenge non-trivial (Fig. 1). First, beam activations on differ- membership CG1 CG1 CG2 CG2 p p t t ent resources share one global budget. Second, finite user buffers change a resource’s marginal value Nonadjacent Nonadjacent membership membership p p t t after earlier assignments satisfy part of theu demand. Third, compatibility-group (CG) sharing links u u uu u u uu u u u the selected user subset to a cardinality-dependent rate penalty. Together, binary beam masks and Buffer BuBuffer Bu p p InclusiveInclusive t t Nearly fullNearly full set-valued user assignments create a search space in which one-pass construction can miss useful span span p p t t combinations and exhaustive search is impractical. 3

4

3

3

1

1

5

4

4

6

2

2

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.

2

R ELATED W ORK

Joint beam and resource allocation has been studied in several settings. Multiuser OFDM work allocates subcarriers, bits, and power to minimize transmit power (Wong et al., 1999). For integrated terrestrial–satellite networks, hybrid beamforming and user scheduling are designed to maximize sum rate and energy efficiency (Peng et al., 2021), and learning-based schedulers address massiveMIMO scheduling under fairness constraints (An et al., 2023). 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 (Liang et al., 2025), while beam-pattern and timeslot design minimizes transmit power subject to traffic demand (Kim et al., 2025). Other studies balance load and avoid interference across multiple satellites (Zhao et al., 2025), assign frequencies across cooperating satellites (Wang et al., 2024), or allocate time, frequency, and space dynamically to reduce supply–demand gaps (Tian et al., 2024). Beam-pattern selection and user scheduling for uneven traffic are studied in (Lei et al., 2024), and low-complexity interference approximations keep beam scheduling tractable as the number of beams grows (Zhao et al., 2026b). 2

Preprint

User selection and sharing add a further layer of coupling. Representative formulations combine user grouping with beam scheduling (Xu et al., 2025), graph-based user clustering with two-stage beamforming (Song et al., 2024), learning-based fair user scheduling designed jointly with precoding (Chang et al., 2025), or user grouping with power and beamforming in NOMA–ODDM integrated sensing and communication (Sultana et al., 2025). Interference-aware graph partitioning further treats user allocation as a weighted graph problem (Lu et al., 2026). Service- and efficiency-oriented designs extend this line. Energy-efficient beam hopping is addressed with a two-step genetic algorithm and a greedy alternative (Taksande et al., 2026), and service-aware beam hopping combines satellite-image features with deep reinforcement learning when the demand distribution is unknown (Xu et al., 2026). Hierarchical deep reinforcement learning reduces the age of information in beam-hopping networks (Xie et al., 2025), a graph-neuralnetwork and Lyapunov framework performs scheduling and hybrid precoding in cell-free mmWave networks (Chang, 2026), and a data- and model-driven successive convex approximation shortens multi-cell MIMO-OFDM allocation (Zhao et al., 2026a). 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 (Zheng et al., 2025), deadline-aware virtual queues in beam scheduling (Xu et al., 2025), and URLLC latency control under link adaptation (Pocovi et al., 2018) bound when packets must be served, while throughput-optimal policies with queue-stability guarantees (Tassiulas & Ephremides, 1992) 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 (Pisinger & Ropke, 2019). 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.

3

S YSTEM M ODEL AND P ROBLEM F ORMULATION

Let U, R, T , P denote the user, resource, subband, and beam sets, with cardinalities N, K, T, P , respectively. User u has buffer 1 ≤ Bu ≤ 10,000, i.e., a cap on the traffic that counts toward the objective in the same units as q(z); a base link quality γu in dB; and a positive capability cu,p on beam p. Resource r has an explicit membership set Tr ⊆ T , with |Tr | ∈ {1, 2}; two memberships need not be adjacent. Its inclusive span is dr = max Tr − min Tr + 1.

(1)

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

αt,p ≤ L,

Gr ̸= ∅ ⇒

t∈T p∈P

X

αt,p ≥ 1, ∀t ∈ Tr .

(2)

p∈P

Let C1 , . . . , CM 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: M [

Gr ∈ {∅} ∪ {{u} : u ∈ U} ∪

m=1

3

{G : G ⊆ Cm , |G| ≥ 2}.

(3)

Preprint

Table 1: Stepwise mapping from effective link value (dB) to traffic units. z (−∞, −10] q(z) 0

(−10, 0] 8

(0, 3] 24

(3, 10] 90

(10, 15] 120

(15, 20] 162

(20, ∞) 222

A user appears at most once in each Gr , but may be assigned to several resources. For u ∈ Gr , selected capability and effective link value are XX cu,p αt,p c̄u,r (α) =

t∈Tr p∈P

,

dr

zu,r = γu + 10 log10

(4)

1 c̄u,r (α) . + 10 log10 P |Gr | p∈P cu,p

(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} gives dr = 4. Table 1 maps the link value z, in dB, to the traffic 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 ( ) X X F (α, G) = min Bu , q(zu,r ) . (6) u∈U

r:u∈Gr

The allocation problem is the finite combinatorial program max

F (α, G)

s.t.

(2), (3),

α,G

(7) αt,p ∈ {0, 1} ∀(t, p).

Operationally, an output earns utility only if it is feasible and is written out (serialized) before the external deadline D. Before applying the beam budget, the P T binary activations define 2P T masks. PL P T
The budget retains ℓ=0 ℓ 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.

4

F EASIBILITY-P RESERVING T RANSACTIONAL R EFINEMENT

FPTR keeps a complete feasible fallback I0 and a feasible incumbent I, which can be returned at any time. Each bounded operator Rj constructs an isolated candidate C without modifying I and has a cumulative stage cutoff tj . Some operators seed their candidate from I, whereas others reconstruct C from stage-specific masks. An allocation is complete if all required decision fields are present, and feasible if it satisfies the constraints in Section 3. Validator V (A) equals 1 when allocation A passes every model constraint and 0 otherwise. Let τ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 . Formally, FPTR is (I0 , {Rj , tj }Jj=1 , V, F ), where J = 5 is the number of stages and F is the objective in (6). Figure 2 summarizes the cumulative stage schedule and the incumbent-preserving return path. 4.1

A LGORITHM AND C UMULATIVE C ONFIGURATIONS

Figure 2(b) and Algorithm 1 show the common commit-or-discard control flow, whereas Fig. 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, I0 remains; final validation restores I0 before serialization if needed. 4

Preprint

(a) Ordered stages and cumulative cutoffs Base

Global

45 ms

CG

60 ms

Remask

70 ms

Pair

78 ms

84 ms

Same CG

Diversified-mask feasible construction τ= 87 ms

CG-focused masks and vaild sharing

marginal repricing

Search cutoff: 84 ms; reserved tail: 3 ms

Elapsed time includes input parsing.

(b) Shared commit-or-discard gate

Remaining-demand masks and one-resource repair

Launch only if prerequisites hold and τin < tj.

Stage /

Initialize I ← I0

candidate controller

Empty, complete, feasible

Eligible work remaining?

Yes

No

Final validation & serialization

Build isolated candidate C

I stays unchanged during search

Reserved 3-ms tail complete(I) ∧ V(I) = 1?

Full = Base + Global + CG + Remask + Pair

Cutoffs are cumulative, not stage durations.

Skip expired stages

Two-resource ruin-and-recreate

Next attempt / stage

Common transactional gate Complete: complete(C) Feasible: V(C) = 1 τdone(C) < tj Timely: Improving: F(C) > F(I) τdone is measured after validation.

PASS ALL Commit: I ← C

FAIL ANY Discard C; keep I

Serialize and output I

Yes No

Restore I ← I0

A complete feasible incumbent is retained throughout refinement.

Serialize and output I0 100-ms deadline: evaluation only.

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 1 FPTR commit-or-discard refinement 1: Initialize I ← I0 , where I0 is the empty complete feasible allocation. 2: for each stage j in the order Base, Global, CG, Remask, Pair do 3: Record stage-entry time τin ; if τin ≥ tj then continue. 4: Construct isolated candidate C ← Rj (I) without modifying I. If C is complete, strictly improving, and before tj , evaluate V (C) and record τdone (C) when it returns. 5: if C passes (9) then I ← C; otherwise discard C. 6: end for 7: if ¬ complete(I) or V (I) = 0 then restore I ← I0 . 8: Serialize and return I.

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. 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. 4.2

E XACT L OCAL CG P RIMITIVE

Once the mask, the resource r, the traffic retained on the other resources, and the sharing cardinality s are fixed, the marginal gain of each user does P not depend on which other users are selected. For an unused or emptied resource r, let Yu = κ̸=r:u∈Gκ q(zu,κ ) be the unclipped traffic that user u receives from the other resources. For fixed CG Cm and sharing cardinality s, define (s) (s) δu,r = min{Bu , Yu + q(zu,r )} − min{Bu , Yu }. (s)

Here zu,r is (5) with |Gr | = s. 5

(8)

Preprint

Table 2: Cumulative configurations and stage cutoffs for an 87-ms budget. Configuration

Cumulative stage added and purpose

BeamFirst Base Global CG Remask Full

independent aggregate-mask reference diversified-mask feasible construction + buffer-aware marginal selection + CG-focused masks and valid sharing + remaining-demand masks and one-resource repair + two-resource ruin-and-recreate

Cutoff (ms) – 45 60 70 78 84

Proposition 1 (Top-s CG selection at fixed cardinality). For fixed α, unused or emptied r, retained traffic Y on the other resources, group Cm , and integer 2 ≤ s ≤ |Cm |, a size-s subset that maximizes (s) incremental traffic is formed by the s users with the largest δu,r . Proof. For fixed s, the sharing penalty is the same for every size-s subset, so the incremental traffic P (s) of S is u∈S δu,r . This sum is maximized by taking the s largest terms. Including the singleton scan, one fixed-resource, fixed-mask query costs O(N + multiplied by Kfree when all free resources are scanned. 4.3

2 m gm log gm ),

P

T RANSACTIONAL G ATING AND F EASIBILITY I NVARIANT

Let I be the feasible incumbent and C an isolated candidate for stage j. Candidate C replaces I if and only if complete(C) ∧ τdone (C) < tj ∧ V (C) = 1 ∧ F (C) > F (I). (9) Here τ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 V . Thus, entering a stage or merely completing candidate construction before tj is insufficient: validation must also finish before the cutoff. The four conditions exclude partial, expired, infeasible, and non-improving candidates. As noted in Section 1, “transactional” refers only to this whole-candidate commit-or-discard rule. Lemma 1 (Feasible-incumbent invariant). Assume that I0 is feasible and validator V is sound for the stated constraints. After every gate operation and immediately before serialization, incumbent I is feasible. Proof. The base case holds because I0 is feasible. Rejection leaves the incumbent unchanged, while acceptance requires V (C) = 1; induction therefore preserves feasibility. Final validation retains I or restores I0 . 4.4

RUNTIME B UDGETING AND T ERMINATION B EHAVIOR

Let Γ denote the total internal budget. The timer starts before input parsing, and τtail = 3 ms is reserved for validation and serialization when Γ ≥ 20 ms. Let ρ = (45, 60, 70, 78, 84) be the cumulative cutoffs of Table 2. Stage j uses cutoff tj = (Γ − τtail )ρj /84, which rescales them to the search window Γ − τtail and equals ρj at Γ = 87 ms. At Γ = 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.

5

E XPERIMENTAL E VALUATION

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). 6

Preprint

Table 3: Fixed main regimes; each contains 30 consecutive seeds. Regime

N

Small balanced 20 Medium long-tail 50 Medium tight 50 Large mixed 100 Large nonadjacent 100

5.1

K

P

T

L

L/(P T )

18 8 4 14 36 16 9 46 36 16 9 26 72 32 18 127 72 32 18 92

0.44 0.32 0.18 0.22 0.16

P ROTOCOL

The single-threaded C++17 scheduler (g++ 13.3, -O2) ran on Linux 6.8 and a 2.30-GHz Xeon E52686 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 Fei,m = median5j=1 Fi,m,j and gi (A, B) = (Fei,A − Fei,B )/Fei,B , defined when Fei,B > 0. Reported percentages first average gi 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) (Ropke & Pisinger, 2006), tabu search (Glover, 1989), a genetic algorithm (GA) (Srinivas & Patnaik, 1994), simulated annealing (SA) (Kirkpatrick et al., 1983), iterated local search (ILS) (Lourenço et al., 2003), and GRASP (Feo & Resende, 1995), rather than reproductions of particular published solvers. 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. 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. 7

Preprint

BeamFirst

Cumulative gain over Base (%)

a

3

Base

Global

CG

Remask

b

Ordered stage gain

Full

Scenario-wise Full gain

Small bal.

n = 150; median of 5 fixed order; losses = 0

Med. long-tail

2

Med. tight

Δ+0.25

Δ+0.59

1

Large mixed

Δ+0.49 Δ+0.44

0 Base

Overall: Base +1.79% BeamFirst +3.83%

Large non-adj. Glob.

CG

Rem.

Pair

0

2

4

6

8

10

Full traffic gain (%)

d

Budget trade-off labels: wall p95 (ms) 87.3

60.4 40.3

1

0 20

40

60

80

1.00

Runtime ECDF (87 ms)

0.75

2 ECDF

Gain vs 20 ms (%)

3

0.50 0.25

100 ms

c

0.00

100

0

Search target (ms)

20

40

60

80

100

Solver wall time (ms)

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.

Table 4: Matched external-baseline comparison at Γ = 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. Baseline

W/T/L

ALNS Tabu GA SA ILS GRASP

134/5/11 139/4/7 127/2/21 137/4/9 137/4/9 140/2/8

Mean rel. Deadline misses gain (%) 95% CI (%) (of 750 runs) 7.80 7.77 6.68 7.90 8.35 7.61

7.03–8.56 7.01–8.52 5.91–7.47 7.19–8.58 7.53–9.13 6.88–8.33

74 18 44 15 41 27

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 (Fig. 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. 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) and one larger case with (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 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. 8

Preprint

BeamFirst

Traffic gain over Base (%)

8

Global

CG

Remask

b

CG-size stress coverage co-varies

6

Gap to optimum (%)

a

Base

4

2

0 2 26

5 36

10 15 64 83 CG size / Full p95 (ms)

40

Full

Exact gaps (11 core + 1 wider) ⋄ mean

⋆ wider

30

20

10

0

20 88

Beam 7/12

Base 8/12

Glob. 8/12

CG 8/12

Rem. 8/12

Full 8/12

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 commitor-discard gate protects the output only when the program terminates normally; it does not cover crashes or forced termination.

6

D ISCUSSION AND C ONCLUSION

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 strictimprovement 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. 9

Preprint

C ODE AND DATA AVAILABILITY Source code: GitHub repository; experimental data: dataset archive. Additional evidence and reproducibility details are provided in Appendix A.

R EFERENCES 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. 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. 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. 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. Fred Glover. Tabu search—part i. ORSA Journal on Computing, 1(3):190–206, 1989. doi: 10.1287/ ijoc.1.3.190. 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. 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. 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. 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. 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. 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. 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. David Pisinger and Stefan Ropke. Large neighborhood search. In Michel Gendreau and JeanYves Potvin (eds.), Handbook of Metaheuristics, pp. 99–127. Springer, 3rd edition, 2019. doi: 10.1007/978-3-319-91086-4_4. 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. 10

Preprint

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. 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. M. Srinivas and Lalit M. Patnaik. Genetic algorithms: A survey. Computer, 27(6):17–26, 1994. doi: 10.1109/2.294849. 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. 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. 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. 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. 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. 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. 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. 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. 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 ICMTAE, pp. 536–542, 2025. doi: 10.1109/ICMTAE66890.2025.11427856. 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. 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. 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.11555755. 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. 11

Preprint

A

E VIDENCE AND R EPRODUCIBILITY S UMMARY

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. A.1

R EADING C ONVENTIONS AND S TATISTICAL U NITS

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 i and method m, let Fi,m,j be the credited traffic from repeat j. The quality unit used in the tables is Fei,A − Fei,B Fei,m = medianj=1,...,5 Fi,m,j , gi (A, B) = . (A.1) Fei,B 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. A.2

E XECUTION ACCOUNTING AND C ONFIGURATION -L EVEL R ESULTS Table A1: Formal internal launch accounting; valid outputs passed independent checks. Suite Main Budget sweep CG stress Exact calibration Total

Instances

Conditions

Repeats

150 150 50 12 –

6 4 3 6 –

5 5 5 5 –

Launches

Valid

Misses

4,500 4,500 3,000 3,000 750 750 360 360 8,610 8,610

0 0 0 0 0

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. A.3

M ATCHED E XTERNAL -BASELINE S UITE

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. 12

Preprint

Table A2: Full versus six independent external baselines at the matched 87-ms main condition. Baseline

W/T/L

ALNS Tabu GA SA ILS GRASP

134/5/11 139/4/7 127/2/21 137/4/9 137/4/9 140/2/8

Mean rel. Main misses/ gain (%) 95% CI (%) 750 runs 7.80 7.77 6.68 7.90 8.35 7.61

7.03–8.56 7.01–8.52 5.91–7.47 7.19–8.58 7.53–9.13 6.88–8.33

74 18 44 15 41 27

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. Table A3: Main-set quality and wall time over 150 five-run instance medians. Configuration BeamFirst Base Global CG Remask Full

Mean Fe 13467.89 13662.15 13732.17 13796.05 13873.17 13898.13

Rel. to Wall p50 Base (%) (ms) -1.82 +0.00 +0.44 +0.88 +1.54 +1.79

4.23 15.75 27.06 46.40 51.44 60.28

Wall p95 Worst (ms) (ms) 7.71 22.68 62.12 73.30 81.35 87.29

8.82 31.50 64.40 78.09 82.85 92.14

Misses/ runs 0/750 0/750 0/750 0/750 0/750 0/750

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. 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. A.4

RUN -L EVEL S TABILITY AND S TAGE 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 (Section 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 13

Preprint

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

n/5n

CG

Remask

Pair

small-balanced 30/150 2/10 8/40 medium-longtail 30/150 18/90 11/55 medium-tight 30/150 7/35 3/15 large-mixed 30/150 27/135 10/49 large-nonadjacent 30/150 18/90 2/16 Overall 150/750 72/360 34/175

Global

5/25 17/85 17/85 0/0 0/0 39/195

3/15 23/115 14/70 0/0 0/0 40/200

score can still improve when accepted changes are sparse, provided that each accepted change is feasible and strictly better. A.5

E XACT C ALIBRATION AND I NDEPENDENT AUDIT Table A5: Exact calibration; BF=BeamFirst; W01/C02–C12=seeds 20281001–20281012. Case

F ⋆ BF Base

Full

Gap Case

F⋆

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

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 compatibilitygroup 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. A.6

B UDGET, CG S TRESS , AND A RTIFACT I NTEGRITY

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.

14

Related documents

• FSEC Meeting Minutes May 8, 2026#347231
• FSEC Meeting Minutes May 1, 2026#347232
• Better Late Than Never: Online Flow Time Scheduling with Online Estimates#984328
• A $1/2$-Approximation for Pandora's Problem with Deadlines#1298271
• frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study#632867