Online Load Balancing on Unrelated Machines

For every pair of natural numbers $n$ and $m$, every instance $I$ consisting of a proof $0<m$, a real load $p_{ij}$ for each job $i\in\{0,\ldots,n-1\}$ and machine $j\in\{0,\ldots,m-1\}$, and proofs $p_{ij}\ge 0$, every function $y$ assigning a real number $y_{ij}$ exactly to each eligible pair $(i,j)$ with $p_{ij}\le 1$, and every proof of the following compound premise: $y_{ij}\ge0$ for every eligible pair, $\sum_{i:\,p_{ij}\le1}p_{ij}y_{ij}\le1$ for every machine $j$, $\sum_{j:\,p_{ij}\le1}y_{ij}\le1$ for every job $i$, and additionally $\sum_{j:\,p_{ij}\le1}y_{ij}=1$ for every job $i$, the theorem asserts the right-nested conjunction that the deterministic run described below has final failure marker $\mathrm{none}$, and that both every job $i$ has some machine $j$ with final assignment entry $\operatorname{some}(j)$ and every machine $j$ has final assigned normalized load at most $\ln(3m)/\ln(3/2)$. The external $y$ is defined only on eligible pairs—there are no values for ineligible pairs—and is used only in the premise, not by the run. The run begins with every machine weight equal to $1/(2m)$, every job assignment equal to $\mathrm{none}$, every job slack equal to $0$, every entry of a separate internal rectangular dual array equal to $0$, and failure marker $\mathrm{none}$, and processes the jobs once each in the order $0,\ldots,n-1$. At an arrival $i$, a state whose failure marker is already nonempty is left unchanged; otherwise the run first tests whether the eligible set $E_i=\{j:p_{ij}\le1\}$ is empty or whether some current machine weight $x_j$ satisfies the strict inequality $1<x_j$, and if either condition holds it changes only the failure marker to $i$. If neither holds, it sorts $E_i$ by the natural order of the finite machine indices and deterministically takes an argmin of $p_{ij}x_j$; the total definition also marks failure at $i$ if that choice nevertheless returns no machine. When it returns a machine $\ell$, writing $p=p_{i\ell}$ and $x=x_\ell$ for the old weight, the transition changes only $x_\ell$ to $x(1+p/2)$, the assignment of $i$ to $\operatorname{some}(\ell)$, the slack of $i$ to $1-px$, and the internal dual entry at $(i,\ell)$ to $1$, retains all other entries, and leaves the failure marker $\mathrm{none}$; the process’s recorded decision is the resulting assignment entry for $i$, while its final state is obtained by iterating these state transitions through the whole arrival list. “Succeeded” here means exactly that this final marker is $\mathrm{none}$, with no additional post-run overweight test, and “assigns all” means exactly $\forall i\,\exists j$, the final assignment of $i$ is $\operatorname{some}(j)$. The final assigned load on $j$ is exactly the finite sum \sum_{i=0}^{n-1}\bigl(p_{ij}\ \text{if the final assignment of \(i is }\operatorname{some}(j),\ \text{and }0\text{ otherwise}\bigr)), and its asserted bound is the unrounded real quotient $\ln(3m)/\ln(3/2)$ for every $j$. Although $m$ is universally quantified over natural numbers, $m=0$ admits no such instance because it would require $0<0$, so that binder case has no $I$; when $n=0$, the eligible-pair type and $y$ are empty, all per-job unit-mass conditions and the assignment conclusion are vacuous, the machine dual sums and final loads are empty sums $0$, no transition occurs, and the load conclusion says $0\le\ln(3m)/\ln(3/2)$ for every machine. If $n>0$ and any job has no eligible machine, its required unit dual mass is the empty sum $0=1$, so no proof of the premise can be supplied and the theorem has no applicable premise in that case; more generally, whenever no such feasible unit-mass $y$ exists, the hypothesis is uninhabited.