NP-Hard Scheduling

1n jobs, m identical machines, minimise makespan

An identical-processor instance is n jobs with processing times t_1,\ldots,t_n and m machines that are interchangeable — any job may run on any machine, one job per machine at a time, no preemption. The makespan C_{\max} is the time the last machine becomes free. The optimisation problem is to assign jobs to machines so C_{\max} is as small as possible.

A trivial lower bound is C_{\max} \ge \max(\max_i t_i, \lceil(\sum t_i)/m\rceil): no machine can finish a job shorter than the job, and m machines cannot beat the average load. For m=1 the bound is the whole story — C_{\max} = \sum t_i in any order.

Figure. Two interchangeable machines. Makespan is the later of the two finish times, not the sum of both loads.

Read one instance

1. JobsA list of times. No machine names, no per-job route.
2. Machinesm copies of the same processor.
3. ScoreC_{\max} = max of the m machine loads (sums of the jobs assigned to them).

2Two machines, target T: that is PARTITION

PARTITION asks: given positive integers a_1,\ldots,a_k, can they be split into two subsets with equal sum? The 2-processor decision 'is there a schedule with C_{\max} \le T?' on times a_1,\ldots,a_k with T = (\sum a_i)/2 (when that T is an integer) is the same question: each subset is one machine's load, and both loads \le T forces both loads = T.

That map is polynomial (it copies the numbers) and you can finish it by hand. Horowitz, Sahni and Rajasekaran place multiprocessor scheduling with the NP-hard problems; PARTITION is the m=2 reason this topic will actually compute. We do not invent a reduction for general m or a Cook-style SAT gadget.

Figure. Left: equal loads 6 and 6, a PARTITION yes. Right: loads 7 and 5, a PARTITION no. Bar lengths are schematic, not 6:7 scale.

The map you can finish

1. From PARTITIONIntegers a_i. Let T = (\sum a_i)/2 when even.
2. To 2-processor decisionJobs of times a_i, m=2, budget T.
3. Yes iff yesA partition is a pair of machine loads each equal to T.

3LPT is a heuristic, not the optimum

Longest-processing-time (LPT) list scheduling sorts the jobs by decreasing t_i and always starts the next job on a machine whose current load is smallest. It is the rule you actually run. It is not guaranteed to hit the optimum.

On times 3, 3, 2, 2, 2 and m=2 — the PARTITION yes-instance — LPT gives loads 3+2+2=7 and 3+2=5, so C_{\max}=7. The partition \{3,3\} and \{2,2,2\} has C_{\max}=6. LPT missed the optimum. Graham's worst-case ratio for LPT is a named theorem in the literature; this topic does not invent or re-prove it.

Figure. LPT on 3,3,2,2,2 with m=2 places 3 then 3, then 2 and 2 on the lighter machine, then the last 2 on M1 after a tie. Loads 7 and 5, Cmax=7. The partition {3,3} and {2,2,2} has Cmax=6. Same jobs; LPT missed the optimum.

LPT on 3,3,2,2,2

1. SortAlready 3, 3, 2, 2, 2.
2. First four3 on M1, 3 on M2, 2 on M1 (loads 5 and 3), 2 on M2 (loads 5 and 5).
3. Last 2Tied loads: the first machine takes it. Loads 7 and 5. C_{\max}=7.

LPT list scheduling

def lpt(times, m):
    times = sorted(times, reverse=True)
    load = [0] * m
    for t in times:
        k = min(range(m), key=lambda i: load[i])
        load[k] += t
    return max(load), load

4Job shop: each operation names its machine

A job-shop instance has n jobs and m named machines. Job j is a sequence of operations (M_{j,1}, t_{j,1}), (M_{j,2}, t_{j,2}), \ldots that must run in that order. Two operations cannot occupy the same machine at the same time. Machines are not interchangeable: an operation that names M_2 cannot run on M_1.

That is a different model from identical processors (no machine names, any job on any machine) and from job sequencing with deadlines (one machine, unit jobs, profit). The 2-by-2 shop J1: (M_1,2) then (M_2,1); J2: (M_2,2) then (M_1,1) has makespan 3 if both jobs start immediately on their first machines.

Figure. Gantt of the 2-by-2 shop. Widths 0.36 versus 0.18 are 2:1, matching the durations 2 and 1. Makespan 3.

Read one job shop

1. Per jobA route: which machine, for how long, in which order.
2. Per machineA sequence of the operations that named it, no overlap.
3. MakespanThe time the last operation in the instance finishes.

5Flow shop is the same route for every job

A flow shop is a job shop in which every job visits the machines in the same order — typically M_1 then M_2 then \cdots then M_m. An open shop drops the per-job order and keeps only 'each job has an operation on each machine'. The running 2-by-2 instance is not a flow shop: J1 wants M_1 then M_2, J2 wants M_2 then M_1.

Horowitz, Sahni and Rajasekaran classify job-shop scheduling as NP-hard. This topic records that classification and does not invent a reduction. What you can check by hand is the model: named machines, per-job routes, no overlap on a machine, precedence inside a job.

Same 2-by-2 Gantt. The new content is the flow-shop row: that Gantt would be illegal in a flow shop that demanded M1-then-M2 for every job.

6What the book’s NP-hard label licenses

The book’s placement of identical-processor scheduling and job shop among the NP-hard problems is a licence to stop looking for a polynomial algorithm that works on every instance, unless you are also trying to prove P = NP. It is not a licence to call a 5-job 2-machine instance 'impossible', and it is not a proof we re-derived in this topic except for the m=2 / PARTITION map.

Honest tools: exact search or IP on small n (the 3,3,2,2,2 instance is enumerable), LPT or other list rules when you need a schedule now, and special cases you can actually solve (m=1; 2-colouring-style structure is the wrong analogue here). Do not invent a SAT-to-job-shop gadget in an exam you cannot finish.

Same 'do this / do not chase that' idea as the graph-NPC licence table, specialised to m=1, LPT, and job shop.