Ordering the Migration: Precedence-Aware Scheduling of Post-Quantum Cryptography Under Harvest-Now-Decrypt-Later Exposure

A post-quantum migration programme must order many assets with unequal effort and prerequisites (a service cannot move before the library, CA or HSM beneath it). We formalise the ordering as single-resource scheduling with precedence constraints and a convex, asset-specific loss: the expected harvest-now-decrypt-later (HNDL) volume that accrues until each asset migrates, under an assumed quantum-arrival curve. The problem is NP-hard even when the curve is flat. Prior work on cost-of-delay ordering covers constant and time-varying rates with unit durations and no prerequisites; we add heterogeneous effort and precedence. We show that ranking by a static score and then performing blockers when forced can be Omega(k) times worse than optimal for a class of weight-monotone scores. In simulation (exact optimum on 480 small instances; 240 larger instances with real PyPI dependency topology and generated graphs), the decisive ingredient is precedence awareness, not any one algorithm: two precedence-aware heuristics (a Sidney-decomposition baseline and a simpler ancestor-closure heuristic, AC-Smith), each with local search, stay within about 1% of the optimum on average, while a static ranking given the same local-search budget is 7.6% above it on small instances and, at n=100-600, AC-Smith lowers its modelled exposure by 26-39%. With no precedence edges, the static-score, myopic, Sidney and AC-Smith policies with local search all land within 0.024% of the best found. All data are simulated under a hypothetical loss model; we state what this does and does not show.