Load Balancing and Makespan

Assign $n$ jobs to $m$ machines minimising the makespan — the completion time of the busiest machine. NP-hard even for $m=2$ (it contains partition).

Greedy: list scheduling

Assign each job to the currently least-loaded machine.

long long makespan(vector<long long> jobs, int m) {
    priority_queue<long long, vector<long long>, greater<>> load;
    for (int i = 0; i < m; i++) load.push(0);
    for (long long p : jobs) {
        long long l = load.top(); load.pop();
        load.push(l + p);
    }
    long long best = 0;
    while (!load.empty()) { best = max(best, load.top()); load.pop(); }
    return best;
}

Approximation ratio: $2-\frac{1}{m}$ (Graham, 1966).

Proof sketch. Let $M^{\ast }$ be the optimal makespan and consider the machine finishing last, whose final job has length $p$. Before that job started, that machine was the least loaded, so its load was at most the average $\frac{1}{m}\sum p_j\le M^{\ast }$. Also $p\le M^{\ast }$. Hence the makespan is at most $M^{\ast }+M^{\ast }=2M^{\ast }$; a sharper accounting gives $2-\frac{1}{m}$. ∎

LPT — sort longest first

Sorting jobs in decreasing order before list scheduling improves the ratio to

$\frac{4}{3}-\frac{1}{3m}.$

One line of extra code for a substantially better guarantee, and in practice it is usually within a few percent of optimal.

sort(jobs.rbegin(), jobs.rend());          // then run list scheduling

Exact methods

$n$	Method
$\le 20$	bitmask DP over assigned jobs
$\le 40$, $m=2$	meet in the middle
$\le 50$, $m=2$	complete Karmarkar-Karp
small $\sum p_j$	subset-sum DP with a bitset
moderate	binary search the makespan + a feasibility check
larger	branch and bound with LPT as the incumbent

Binary search + bin packing check

Binary search the makespan $T$ and ask “can all jobs fit into $m$ bins of capacity $T$?” — a bin-packing feasibility question, itself NP-hard but often answered quickly by a backtracking search with:

• jobs sorted descending,
• skipping equal-length jobs already tried in the current position,
• placing each job only in the first empty bin among identical empty bins (symmetry breaking),
• pruning when the remaining jobs cannot fit in the remaining capacity.

This handles $n\le 30$-$50$ comfortably and is the usual contest approach.

Approximation schemes

A PTAS exists: round job sizes, handle the $O(1)$ “large” jobs exactly by enumeration, and fill in the small ones greedily. $(1+\epsilon )$-approximate in $O(n)$ time for fixed $\epsilon$ and $m$. Of theoretical interest — the constants are impractical.

Related problems

Problem	Note
Bin packing	fewest bins of fixed capacity; First-Fit-Decreasing is $\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$
Partition	$m=2$, decide if a perfect split exists — see Subset Sum
Multiway number partitioning	the same problem, phrased numerically
Scheduling on unrelated machines	job $j$ takes $p_{ij}$ on machine $i$; 2-approximation by LP rounding (Lenstra-Shmoys-Tardos)
Scheduling with precedence	Graham’s list scheduling is still $(2-\frac{1}{m})$
Online load balancing	greedy is $(2-\frac{1}{m})$-competitive; no online algorithm beats $\approx 1.85$
Minimise the sum of completion times	easy: SPT, or round-robin across machines

That last row is the useful contrast: minimising the maximum load is NP-hard, but minimising the total completion time is a simple greedy. As with lateness, swapping max for sum changes the difficulty entirely — in the opposite direction this time.

Bin packing heuristics

Heuristic	Ratio
Next Fit	2
First Fit	1.7
Best Fit	1.7
First Fit Decreasing	$\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$
Best Fit Decreasing	same

FFD is the practical default: sort descending, place each item in the first bin that fits.

See also: Karmarkar-Karp · Subset Sum · Approximation Algorithms