Organizations: Department of Network Intelligence, Pengcheng Laboratory, Shenzhen, China · School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen Campus, Shenzhen, China
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.
Figures & tables
Figure 1: Schematic overview of one scheduling interval. Beam activation, user assignment, finite demand, and resource sharing must be resolved before the execution deadline.
z
(−∞,−10]
(−10,0]
(0,3]
(3,10]
(10,15]
(15,20]
(20,∞)
q(z)
0
8
24
90
120
162
222
Table 1: Stepwise mapping from effective link value (dB) to traffic units.
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.
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 .
Algorithm 1 FPTR commit-or-discard refinement
Configuration
Cumulative stage added and purpose
Cutoff (ms)
BeamFirst
independent aggregate-mask reference
–
Base
diversified-mask feasible construction
45
Global
+ buffer-aware marginal selection
60
CG
+ CG-focused masks and valid sharing
70
Remask
+ remaining-demand masks and one-resource repair
78
Full
+ two-resource ruin-and-recreate
84
Table 2: Cumulative configurations and stage cutoffs for an 87-ms budget.
Regime
N
K
P
T
L
L/(PT)
Small balanced
20
18
8
4
14
0.44
Medium long-tail
50
36
16
9
46
0.32
Medium tight
50
36
16
9
26
0.18
Large mixed
100
72
32
18
127
0.22
Large nonadjacent
100
72
32
18
92
0.16
Table 3: Fixed main regimes; each contains 30 consecutive seeds.
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.
Baseline
W/T/L
Mean rel. gain (%)
95% CI (%)
Deadline misses (of 750 runs)
ALNS
134/5/11
7.80
7.03–8.56
74
Tabu
139/4/7
7.77
7.01–8.52
18
GA
127/2/21
6.68
5.91–7.47
44
SA
137/4/9
7.90
7.19–8.58
15
ILS
137/4/9
8.35
7.53–9.13
41
GRASP
140/2/8
7.61
6.88–8.33
27
Table 4: Matched external-baseline comparison at Γ=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.
Figure 4: Stress and calibration: (a) co-varying CG size and coverage and (b) exact optimality gaps on 12 cases.