iv. Scheduling and Partitioning

Scheduling problems are a map of what’s easy and what’s NP-hard. On one machine, almost everything polynomial is “sort by the right key + exchange argument”. Release times, sums with weights, or several machines usually make it hard. The partitioning problems at the end are the NP-hard cousins.

The single-machine landscape

Notation $\alpha \mid \beta \mid \gamma$: machines | constraints | objective. $C_j$ is completion time, $L_j=C_j-d_j$ lateness, $T_j=\max (0,L_j)$ tardiness, $U_j=[C_j>d_j]$, $E_j=\max (0,-L_j)$ earliness. Minimising $\max L_j$ and $\max T_j$ are the same problem (both are maximised by the same late job), but swap “max” for “sum” and the difficulty changes completely: minimising $\sum T_j$ or $\sum w_j{U}_j$ is NP-hard even though $\max L_j$ (EDD) is easy.

Preemption often turns an NP-hard problem easy — compare each non-preemptive row above with its preemptive counterpart ($1\mid r_j\mid L_{\max }$ NP-hard vs. $1\mid r_j,pmtn\mid L_{\max }$ solved by preemptive EDD; $1\mid r_j\mid \sum C_j$ NP-hard vs. SRPT; $P\mid \mid C_{\max }$ NP-hard vs. McNaughton). Preemptive EDD with release times works by running, at every moment, the available job with the earliest deadline, preempting whenever a more urgent job arrives — implemented as a priority queue keyed by deadline, processed in release-time event order. When a problem statement allows preemption, checking the preemptive row first is usually the intended solution.

Problem	Rule	Cost
$1\mid \mid \sum C_j$	SPT: shortest first	$O(n\log n)$
$1\mid \mid \sum w_j{C}_j$	Smith: $p_j/w_j$ ascending	$O(n\log n)$
$1\mid \mid L_{\max }$	EDD: earliest deadline first	$O(n\log n)$
$1\mid \mid \sum U_j$	Moore-Hodgson	$O(n\log n)$
$1\mid prec\mid f_{\max }$	Lawler: build the schedule backwards	$O(n^2)$
$1\mid r_j,pmtn\mid L_{\max }$	preemptive EDD	$O(n\log n)$
$1\mid r_j,pmtn\mid \sum C_j$	SRPT: shortest remaining time	$O(n\log n)$
$1\mid \mid \sum w_j{U}_j$	NP-hard; knapsack DP over deadlines	pseudo-poly
$1\mid \mid \sum T_j$	NP-hard; Lawler’s pseudo-poly DP
$1\mid r_j\mid L_{\max }$, $1\mid r_j\mid \sum C_j$	NP-hard (non-preemptive)
$F2\mid \mid C_{\max }$	Johnson’s rule	$O(n\log n)$
$F3\mid \mid C_{\max }$, $P2\mid \mid C_{\max }$	NP-hard
$P\mid pmtn\mid C_{\max }$	McNaughton: $\max (\max p_j,\sum p_j/m)$, wrap-around	$O(n)$

Proof: McNaughton's rule achieves the preemptive makespan lower bound

Lower bound. No machine can finish before the single longest job completes ($C_{\max }\ge {\max }_j{p}_j$), and the total work $\sum p_j$ split across $m$ machines means some machine does at least $\frac{1}{m}\sum p_j$ of it ($C_{\max }\ge \frac{1}{m}\sum p_j$). So $C_{\max }\ge \max ({\max }_j{p}_j,\frac{1}{m}\sum p_j)=:T$. Achievability. Lay all jobs end to end on a single conceptual timeline of total length $\sum p_j\le mT$, then cut this timeline into $m$ segments of length exactly $T$ each (padding the last with idle time), assigning segment $k$ to machine $k$: a job may straddle a cut, in which case it is preempted and continues on the next machine at the same point in time. This is always valid because $T\ge {\max }_j{p}_j$ guarantees no job is longer than one full segment, so a job straddles at most one cut (never wraps around twice). Every machine’s segment has length exactly $T$, so $C_{\max }=T$, matching the lower bound. $■$

EDD proof: an adjacent inversion ($d_i>d_j$, $i$ first) can be swapped without increasing $\max L$: $j$ finishes earlier, and $i$ now finishes when $j$ did, but with a later deadline.

Proof: EDD minimises maximum lateness, and SPT minimises $\sum C_j$

EDD. Take any schedule with an adjacent inversion: jobs $i$ then $j$ with $d_i>d_j$, finishing the pair at time $t$ ($i$ at $t-p_j$, $j$ at $t$). Swap them: $j$ now finishes at $t-p_j<t$, so $L_j$ strictly decreases; $i$ now finishes at $t$, giving $L_i^{\text{new}}=t-d_i$. Since $d_i>d_j$, $t-d_i<t-d_j=L_j^{\text{old}}$, and $L_j^{\text{old}}\le \max L$ before the swap — so $i$‘s new lateness is below the old maximum too. No other job’s completion time changes (the pair occupies the same total time span as before). So the swap never increases $\max L$, and repeating removes every inversion, reaching EDD order without ever increasing the maximum lateness — EDD is optimal. SPT. For $\sum C_j$, take an adjacent inversion: jobs $i$ then $j$ with $p_i>p_j$, with $i$ finishing at $C_i=t-p_j$ and $j$ at $C_j=t$ (both measured from the same start, $t$ being when the pair is done). Every other job’s completion time is unaffected by swapping only this pair. After swapping to $j$ then $i$: $j$ finishes at $t-p_i$ and $i$ finishes at $t$. The pair’s contribution to $\sum C_j$ changes from $(t-p_j)+t$ to $(t-p_i)+t$, a decrease of $p_i-p_j>0$. So every adjacent inversion strictly decreases $\sum C_j$ when swapped, meaning any schedule not already in SPT order can be strictly improved — hence SPT (no inversions left) is optimal. $■$

Unit jobs with deadlines and profits

Maximise the total profit of on-time unit jobs. The feasible sets form a matroid, so greedy by profit works. Two implementations:

// (a) by profit descending, put each job in the latest free slot <= deadline: DSU "free slot"
iota(all(par), 0);                                     // par over slots 0..maxD, slot 0 = none
auto find = [&](auto&& self, int x) -> int { return par[x] == x ? x : par[x] = self(self, par[x]); };
for (auto [p, d] : byProfitDesc) { int t = find(find, min(d, maxD)); if (t) total += p, par[t] = t - 1; }
 
// (b) by deadline ascending, take everything, drop the cheapest when count > deadline
for (auto [d, p] : byDeadline) { pq.push(p); if ((int)pq.size() > d) pq.pop(); }   // min-heap

Feasibility (Hall): a set is schedulable iff for every $t$, at most $t$ of its jobs have deadline $\le t$.

Moore-Hodgson (fewest late jobs)

Process by deadline, keep the on-time set; when the current total time exceeds the deadline, drop the longest job taken so far.

Proof: Moore-Hodgson maximises the number of on-time jobs

Jobs are processed by deadline order, maintaining a tentative on-time set $S$ with jobs run in deadline order among themselves (so $S$ is feasible iff its total processing time is $\le$ every prefix’s deadline, checked incrementally as $t={\sum }_{S}p$ against the newest job’s deadline $d$). Claim: at each point, $|S|$ equals the maximum number of on-time jobs achievable using only the jobs seen so far. By induction: adding a new job either keeps $t\le d$ (feasible, and since it’s the newest deadline, including it can only help — any optimal solution on the extended job set either includes it, matching this case, or doesn’t, in which case the old optimal size still applies and is $\le$ new $|S|$) or forces $t>d$. When forced, dropping the single longest job in $S\cup \{\text{new}\}$ is correct because: any feasible subset of $S\cup \{\text{new}\}$ of size $|S|$ (one less than $|S|+1$) must drop at least one job to bring the total time at or below every relevant deadline, and dropping the longest job minimizes the total time removed for a single drop — among single-job drops, this is the unique way to guarantee the remaining total time is minimized, and a smaller total time can only make later feasibility checks (against larger future deadlines) easier to satisfy, so it dominates any other single-job drop for all future steps simultaneously. Since no other way to reach size $|S|$ (from this one extra job) can leave a smaller remaining total time, dropping the longest job preserves optimality of the running count. $■$

sort(all(jobs));                                       // by deadline
priority_queue<ll> taken; ll t = 0;                    // max-heap of durations
for (auto [d, p] : jobs) { taken.push(p); t += p; if (t > d) t -= taken.top(), taken.pop(); }
// on time: taken.size()

The weighted version (maximise the total weight of on-time jobs) is knapsack-like: sort by deadline, $dp[t]$ = best weight finishing by time $t$, $O(n\sum p)$.

The reusable pattern behind both the unit-jobs profit problem and Moore-Hodgson: process items in a natural order, greedily accept everything, and when a constraint is violated, discard the single least-useful item accepted so far (smallest profit; longest duration; whatever the constraint penalises most). A heap makes the discard $O(\log n)$. The same shape also solves “maximum items within a budget” (drop the most expensive), “attend the maximum number of events” (drop the latest-ending), and IPO/capital problems (a heap of currently-affordable projects).

Johnson’s rule (two-machine flow shop)

Every job runs on A for $a_j$, then on B for $b_j$. Put jobs with $a_j\le b_j$ first in increasing $a_j$, then the rest in decreasing $b_j$. The two-group form is a strict weak order (the single comparator $\min (a_i,b_j)<\min (a_j,b_i)$ is not, with ties).

Proof: Johnson's rule minimises the makespan

The schedule processes jobs in some order, carrying a state $(t_A,t_B)$ = the time each machine becomes free; processing job $k$ updates $t_A\leftarrow t_A+a_k$, then $t_B\leftarrow \max (t_B,t_A)+b_k$. Both updates are non-decreasing functions of the incoming $(t_A,t_B)$ (sums and maxes of non-negative increments), so a smaller incoming state can never lead to a larger final makespan after processing the rest of the sequence. It suffices to show: for any adjacent pair $i$ then $j$, swapping to $j$ then $i$ does not increase the resulting $t_B$ whenever $\min (a_i,b_j)\le \min (a_j,b_i)$ (Johnson’s comparator) — then every inversion against this comparator can be removed by an adjacent swap without increasing the final makespan, so the fully sorted (two-group) order is optimal.
Write $t_B(ij)$ for the value of $t_B$ after processing $i$ then $j$ from entering state $(t_A,t_B)$. Expanding the recurrence twice and simplifying (dropping $\max$‘s dominated term where one candidate is always $\ge$ another, which direct comparison confirms) gives $t_B(ij)=\max (t_B+b_i+b_j,t_A+b_i+b_j+a_i,t_A+a_i+a_j+b_j)$, and symmetrically $t_B(ji)=\max (t_B+b_i+b_j,t_A+b_i+b_j+a_j,t_A+a_i+a_j+b_i)$. The first term is common to both, so write $D=t_A+b_i+b_j$ and $C=t_A+a_i+a_j$; the claim reduces to $\max (D+a_i,C+b_j)\le \max (D+a_j,C+b_i)$ given $\min (a_i,b_j)\le \min (a_j,b_i)$. Case $a_i\le b_j$: then $a_i\le \min (a_j,b_i)$ gives both $a_i\le a_j$ (so $D+a_i\le D+a_j$) and $a_i\le b_i$ (so $(C+b_j)-(D+a_j)=a_i-b_i\le 0$, i.e. $C+b_j\le D+a_j$); both candidates on the left are $\le$ the right-hand max. Case $b_j\le a_i$: then $b_j\le \min (a_j,b_i)$ gives both $b_j\le b_i$ (so $C+b_j\le C+b_i$) and $b_j\le a_j$ (so $(D+a_i)-(C+b_i)=b_j-a_j\le 0$, i.e. $D+a_i\le C+b_i$); again both left candidates are $\le$ the right-hand max. Either way $\max (D+a_i,C+b_j)\le \max (D+a_j,C+b_i)$, proving the swap never increases $t_B$, hence never increases the final makespan. $■$

Verified against a brute force over all permutations on random small instances.

sort(all(ord), [&](int i, int j) {
    bool gi = a[i] <= b[i], gj = a[j] <= b[j];
    if (gi != gj) return gi;
    return gi ? a[i] < a[j] : b[i] > b[j];
});
ll tA = 0, tB = 0;
for (int i : ord) tA += a[i], tB = max(tB, tA) + b[i];   // tB = makespan

The same order solves “resource first spent then regained” problems (need $a_i$ to start, end with $b_i$ more or less).

Three or more machines is NP-hard in general; Johnson’s rule extends cleanly to three machines only in the special case where the middle machine is “dominated” (${\max }_j{a}_j\le {\min }_j{b}_j$ or ${\max }_j{c}_j\le {\min }_j{b}_j$, letting the middle stage’s ordering be ignored).

Lawler (precedences, minimise max penalty)

$f_j$ are non-decreasing functions of completion time, and precedences form a DAG. Build from the end: at time $t=\sum p$, among jobs with no unscheduled successors, put last the one minimising $f_j(t)$; set $t-=p_j$ and repeat. Exchange argument: moving that job to the end only shifts others earlier. $O(n^2)$, or $O(n\log n)$ with a heap when $f$ is lateness.

Proof: Lawler's backward construction minimises ${\max }_j{f}_j(C_j)$

Claim: there is an optimal schedule in which the job chosen in the first step ($j^{\ast }$, minimising $f_j(P)$ among jobs with no unscheduled successors) is last. Let $k$ be whichever job is last in some optimal schedule $O$. Both $j^{\ast }$ and $k$ are eligible to be last (no unscheduled successors — $k$ because it’s last in a valid schedule, $j^{\ast }$ by construction), and $f_{j^{\ast }}(P)\le f_k(P)$ by the choice rule. Modify $O$ by moving $j^{\ast }$ to the last position and shifting every job that was between $j^{\ast }$‘s old position and the end one slot earlier (this respects precedence: removing $j^{\ast }$ cannot violate any predecessor’s constraint since those jobs still finish no later, and $j^{\ast }$ having no unscheduled successors means nothing after it depended on it). Then $j^{\ast }$‘s new cost is $f_{j^{\ast }}(P)\le f_k(P)\le \mathrm{OPT}$, every other job now finishes at or before its old completion time, and since every $f_j$ is non-decreasing, no other job’s cost increases. So the modified schedule has cost $\le \mathrm{OPT}$, is also optimal, and has $j^{\ast }$ last. Recursing — removing $j^{\ast }$ leaves a precedence-respecting problem on the remaining $n-1$ jobs over $[0,P-p_{j^{\ast }}]$ — shows the algorithm’s choice at every step is similarly extendable to an optimum of the remaining prefix; the one-job base case is trivial. $■$

Parallel machines (makespan)

$P\mid \mid C_{\max }$ is NP-hard even for $m=2$ (partition).

Method	Guarantee / use
list scheduling (least loaded machine)	$2-1/m$ approximation
LPT (longest first, then list)	$4/3-1/(3m)$, usually within a few percent of optimal in practice
binary search $T$ + bin-packing backtracking	exact, $n\le 30$-$50$ with symmetry breaking
bitmask DP over assigned jobs	exact, $n\le 20$
subset-sum bitset ($m=2$)	exact for $\sum p\le 10^6$-$10^7$
meet in the middle ($m=2$)	exact, $n\le 40$, huge values, $O(2^{n/2})$
complete Karmarkar-Karp ($m=2$)	exact, $n\le 50$, huge values
branch and bound with LPT as the incumbent	larger $n$, no other exact method fits

Backtracking for bin packing: sort jobs descending; try each job in each bin; skip bins with the same current load as a bin already tried; never open two empty bins for the same job; prune when the remaining sum can’t fit.

Bin packing heuristics: next fit has ratio 2, first fit 1.7, first-fit decreasing $\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$. FFD is the practical default.

Proof: list scheduling is a $(2-\frac{1}{m})$-approximation

Let $M^{\ast }$ be the optimal makespan, and let job $j^{\ast }$ (length $p$) be the last job assigned, placed on the machine that finishes at the overall makespan $C_{\max }=L+p$, where $L$ was that machine’s load just before $j^{\ast }$ was assigned. Since list scheduling always assigns to the currently least-loaded machine, $L$ was the minimum load over all $m$ machines at that instant, so every machine’s load was $\ge L$, giving $mL\le {\sum }_{\text{assigned so far}}{p}_j\le {\sum }_j{p}_j-p$ (the sum over already-assigned jobs excludes $j^{\ast }$). So $L\le \frac{1}{m}({\sum }_j{p}_j-p)$, and $C_{\max }=L+p\le \frac{1}{m}{\sum }_j{p}_j+\frac{m-1}{m}p$. Using the two standard lower bounds $\frac{1}{m}{\sum }_j{p}_j\le M^{\ast }$ (the optimum’s average load) and $p\le M^{\ast }$ (a single job length): $C_{\max }\le M^{\ast }+\frac{m-1}{m}{M}^{\ast }=(2-\frac{1}{m})M^{\ast }$. $■$

A PTAS exists for this problem too: round job sizes, handle the $O(1)$ “large” jobs exactly by enumeration, and fill in the small ones greedily, giving a $(1+\epsilon )$-approximation in $O(n)$ time for fixed $\epsilon ,m$ — of theoretical interest only, the constants are impractical. On unrelated machines (job $j$ costs $p_{ij}$ on machine $i$, not just $p_j$), LP rounding gives a 2-approximation (Lenstra–Shmoys–Tardos); Graham’s list scheduling stays a $(2-\frac{1}{m})$-approximation even with precedence constraints added; and online (jobs revealed one at a time, no revisiting past assignments) greedy list scheduling is $(2-\frac{1}{m})$-competitive, with no online algorithm beating $\approx 1.85$.

Number partitioning

Split numbers into two sets minimising the difference of sums.

Situation	Method
$\sum a\le 10^6$-$10^7$	subset-sum DP with bitset: `b
$n\le 40$, huge values	meet in the middle: sort half-sums, two pointers, $O(2^{n/2})$
$n\le 60$, huge values	complete Karmarkar-Karp (branch: difference or sum the two largest, prune when the largest exceeds the rest)
large $n$, approximate	Karmarkar-Karp differencing

Karmarkar-Karp (largest differencing): repeatedly replace the two largest numbers with their difference. The last number is the discrepancy. For random inputs the expected discrepancy is $n^{-\Theta (\log n)}$, far better than greedy’s $\Theta (1/n)$ — differencing commits only to a relation (“these two end on opposite sides”) and defers the magnitude decision, so each step shrinks the residual fast instead of accumulating greedy’s error. Recover the partition by recording “these two are separated” edges and 2-colouring the resulting tree. Worst-case guarantee: none (it’s a heuristic) — but for the related makespan objective the worst-case ratio is $7/6$. Random partitioning instances show a sharp easy/hard phase transition around $m\approx n$ bits per number, a well-studied phenomenon in the complexity-of-heuristics literature.

Bounded number of distinct values: subset sum with $\sum a=S$ has at most $O(\sqrt{S})$ distinct values, so binary splitting of multiplicities plus a bitset gives $O(S\sqrt{S}/64)$.

Other classic schedules

• Minimise total completion time on $m$ identical machines: SPT, dealt round-robin: the $k$-th largest job overall gets multiplied by $\lceil k/m\rceil$.
• Minimise the sum of waiting times with priorities: Smith’s rule again.
• Tasks with prerequisites and parallel workers, minimise time: NP-hard in general (precedence-constrained scheduling); for trees and unit times, Hu’s algorithm (highest level first) is optimal.
• CPU scheduling with arrival times, preemptive, unit weights: SRPT is optimal for $\sum C_j$.
• Interval-type fixed schedules belong to Interval Problems.