A result on a scheduling problem is a statement about its decision version on words, about algorithms that output schedules, or about online play. Such statements depend on how instances and schedules are written, so they are made relative to a reading of the problem: which words encode which instance, which words write which schedule, and what an online scheduler sees at each time. A reading of a family gives one for every specification. The results of the literature are claims about the standard binary readings; here every result is a proposition about a given reading.

Fix a reading and parameters $\kappa$: functions of the instance and the threshold into the naturals (most depend on the instance only; some, such as the pathwidth of time windows that end at the threshold, depend on both). The decision version on words: a word of an instance, then the sign and absolute value of an integral threshold $D$, is a yes-instance if some feasible schedule has cost at most $D$. Running times are those of the word RAM (lax-496464, lax-808846).

Exact algorithms and hardness. In P: decided in time $c\,(|w|+1)^d$ in the bit size $|w|$. Pseudo-polynomial: in time $c\,(M+1)^e(|w|+1)^d$, where $M$ is the largest number of the word. NP-hard: $NPHardIn$ of lax-496464; strongly NP-hard: NP-hard on the words whose numbers are at most $c\,(\text{length}+1)^d$. In P (pseudo-polynomial) for every fixed value of $\kappa$; FPT, W[t]-hard (strongly: on such words), para-NP-hard: NP-hard for one fixed value.

Running times. An algorithm can be stated with its exact running time, a function $T$ of the instance (of $n$, $m$, $p_{\max}$, the total weight, …): one program halts, writing the answer for the instance and the threshold, within $c\,(T(x)+1)$ instructions on the word of every instance $x$, at every word length $\ell$ with $(|w| + M + 2)^c \le 2^\ell$, where $|w|$ is the length of the word and $M$ its largest number — words of $O(\log)$ bits, as on the word RAM of the literature. Deciding, approximating, approximating with random bits and approximation schemes each have such a form; a submitted algorithm is a program with a proof of one of them. Deciding can also be stated without the constant: one program halts with the answer within exactly $T(x, D)$ instructions, a function of the instance and the threshold, at the same word lengths.

Randomized deciding. The program reads, after the word, at most $c\,(T(x)+1)$ random bits and halts within $c\,(T(x)+1)$ instructions on every choice of them. With bounded error its answer is right for at least two thirds of the choices. With one-sided error it never accepts a no-instance and accepts a yes-instance for at least half of the choices. With zero error (Las Vegas) it is always right and the bound $c\,(T(x)+1)$ holds for the number of instructions averaged over the choices. Repetition turns any of these into error $2^{-k}$ at $k$ times the cost, so the constants $2/3$ and $1/2$ are not essential.

Approximation. A ratio is a function $\rho$ of the instance into the reals. A $\rho$-approximation is a polynomial-time program that on the word of an instance with a feasible schedule writes the word of a feasible schedule costing at most $\rho$ times every feasible schedule; for a maximization problem, whose cost is the negative of its value, the value is at least $\rho$ times every value. A randomized one reads polynomially many random bits; every choice gives a feasible schedule, the average cost is within the ratio, and the running time is polynomial in the worst case or, for an expected-time algorithm, on average over the bits. Approximations may be restricted to the instances of a set. PTAS, EPTAS and FPTAS are as usual; inapproximability below $\rho$ unless P = NP says that if P ≠ NP no $\rho'$-approximation exists for a constant $\rho' < \rho$. An *additive* $\delta$-approximation writes a feasible schedule costing at most every feasible cost plus $\delta$, a function of the instance; an additive scheme does so with $\varepsilon\,\delta$ for every $\varepsilon > 0$, in polynomial time for each fixed $\varepsilon$. A parameterized approximation scheme for a parameter $\kappa$ is one program that writes a $(1 + a/b)$-approximate schedule from the word of an instance followed by $a, b$, in time $f(\kappa + b/a)\,(|w|+1)^d$.

Running times and word size. A running time, upper or lower, is stated with short words, $\ell \ge c \log_2(|u| + M + 2)$; the classes keep the long words of the registered notions and are reached from running times through the transfer theorems. A lower bound is stated for the time plus the length of the shortest word of the instance.

Wide words. An algorithm whose running time $T$ exceeds every polynomial may need words that hold the address of every step, $c\,(T(x)+1) \le 2^\ell$ besides the short words above; this is the standard assumption for such algorithms, whose tables are as large as their running times. Deciding within $O(T)$ with wide words asks the program to work only at those word lengths.

Restrictions. A result may hold on the instances satisfying a predicate $\varphi$ only: it is then a result on the problem restricted to them, read with the same words.

Kept weight. A problem that minimizes the weight of the jobs it rejects (late, or not just in time) is read with the same instances, schedules and costs when a source maximizes the weight it keeps. The kept weight of a schedule is the total weight $W$ of the instance minus its cost. A $\rho$-approximation of the kept weight, for $\rho \le 1$, writes a feasible schedule that keeps at least $\rho$ times the weight of every feasible schedule; schemes keep $1 - a/b$ times it. An online algorithm is $\rho$-competitive for the kept weight, $\rho \ge 1$, if every feasible schedule keeps at most $\rho$ times what the algorithm keeps plus a constant, the convention of the sources on throughput.

Kernels. A kernelization for a parameter is a polynomial-time map on the words of instances that keeps the answer and whose output has size (bit length) and parameter at most $g(\kappa)$ for a computable $g$; a polynomial kernel has $g$ polynomial.

The exponential time hypothesis. A formula is written as the number $n$ of variables followed, for every clause, by its length and its literals, the literal of variable $v$ being $2v+1$ if positive and $2v$ if negative. ETH: for some $q > 0$ no program decides the satisfiability of formulas whose clauses have three literals over variables below $n$ within $c\,2^{\lfloor n/q \rfloor}(|w|+1)^c$ instructions, at the word lengths above. A function $f$ is $o(g)$ if for every rational $\varepsilon > 0$, eventually $f(k) \le \varepsilon\, g(k)$.

Online. A deterministic algorithm is $\rho$-competitive if it is non-anticipative for the revelation and, for some additive constant, its cost is at most $\rho$ times every feasible cost plus that constant; a randomized one is a finite distribution over non-anticipative algorithms. A lower bound $\rho$ says that no algorithm is $\rho'$-competitive for $\rho' < \rho$.