data center schedulers

Abstract: The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is one where the total weight of all late jobs is minimized. The classic dynamic programming algorithm of Lawler and Moore [Manag. Sci., 1969] solves this problem in $O(nd_{\max}^m)$ where $n$ is the number of jobs, $d_{\max}$ is the maximum due date of any job, and $m$ is the number of identical machines. We show that it is sufficient to only compute part of the dynamic program and obtain the running time $\tilde{O}(n + d_{\max}^{m + 1})$ where $\tilde{O}$ suppresses polylogarithmic factors. This affirmatively answers the open question posed by Hermelin, Molter, and Shabtay [INFORMS J. Comput., 2024], whether a running time of $\tilde{O}(n + d_{\max}^2)$ is possible on a single machine.

Abstract: Nominal chip specifications do not capture the compute deliverable by heterogeneous distributed networks under communication, runtime and verification constraints. We formalize D-PIN Standardized Compute Units (D-PIN SCU) as a dynamic metering system for deliverable compute. The system combines five-dimensional resource normalization with topology-aware and runtime-corrected metering. A cluster-scale Roofline model yields a closed-form communication ridge, while runtime factors describe thermal, fault and load effects. We show that runtime deviations cannot be identified from nominal specifications alone. Uniform re-anchoring preserves relative metering results, and a simplex-constrained calibration algorithm estimates resource weights. The framework couples Proof-of-Physical-Work verification to a no-arbitrage condition for over-claiming and electricity-aware pricing. An end-to-end recomputation on the Zhangjiang Science Gate production node covers ten heterogeneous 8-GPU servers totaling 59.5 D-PIN SCU. Billed throughput of approximately 33,000 D-PIN SCU-hours is consistent with the physical upper bound at 78% utilization over 720 hours. Derived metrics are 3.02 kW per D-PIN SCU at the supply-and-distribution design boundary and 0.26 D-PIN SCU-hours per delivered kWh. Empirically calibrated chip values differ materially from datasheet projections; the published calibration is not independently reproducible from vendor specifications. Validation is limited to one production node, and the originality claim concerns the integrated system rather than the SCU terminology or individual components. The framework provides a basis for scheduling, verification and pricing of deliverable compute in distributed heterogeneous networks.