Sources and References

Primary textbook — M. Pinedo, Scheduling: Theory, Algorithms, and Systems (6th ed., Springer, 2022; freely available at the author’s website)

Supplementary texts — S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Jobshop (Ellis Horwood, 1982); E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan & D.B. Shmoys, “Sequencing and Scheduling: Algorithms and Complexity” in Logistics of Production and Inventory (North-Holland, 1993); K.R. Baker, Introduction to Sequencing and Scheduling (Wiley, 1974); D.S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems (PWS, 1997)

Online resources — D.R. Karger, C. Stein & J. Wein, “Scheduling Jobs with Fixed Precedence Constraints” survey; Peter Brucker, Scheduling Algorithms (Springer, 5th ed.); MIT OCW 6.854 Advanced Algorithms (scheduling segments)

Chapter 1: Framework and Notation

1.1 Motivation and Practical Examples

Scheduling problems arise whenever a set of tasks must be assigned to resources over time. Representative instances include:

• Manufacturing: assigning jobs to machines in a factory to minimise total completion time or meet delivery deadlines.
• Computer science: scheduling processes on CPUs or distributed cores to minimise response time or energy consumption.
• Healthcare: assigning nurses to shifts or surgeries to operating rooms subject to legal working-hour constraints.
• Transportation: routing aircraft or railway units, with crew rostering satisfying union rules.
• Project management: coordinating project activities with technological precedence constraints using critical-path methods (PERT/CPM).

Despite this diversity, the mathematical structure is remarkably uniform. A scheduling instance consists of a set of jobs (or tasks, operations) to be processed on a set of machines (or processors, resources). Jobs consume machine time; the goal is to find an assignment of jobs to machines and a sequencing of jobs on each machine that optimises a given performance criterion.

1.2 The Three-Field (Graham) Notation

The standard shorthand for scheduling problems is the α | β | γ notation introduced by Graham, Lawler, Lenstra and Rinnooy Kan (1979). Each field restricts or qualifies the problem:

Machine environments (α field)

Job characteristics (β field)

Multiple entries may appear simultaneously, separated by commas.

Objective functions (γ field)

Let \(C_j\) denote the completion time of job \(j\). Define:

• Makespan: \(C_{\max} = \max_j C_j\)
• Lateness: \(L_j = C_j - \bar{d}_j\); maximum lateness \(L_{\max} = \max_j L_j\)
• Tardiness: \(T_j = \max(C_j - \bar{d}_j, 0)\)
• Unit penalty (lateness indicator): \(U_j = \mathbf{1}[C_j > \bar{d}_j]\)
• Weighted completion time: \(\sum_j w_j C_j\)
• Weighted tardiness: \(\sum_j w_j T_j\)
• Weighted number of late jobs: \(\sum_j w_j U_j\)

1.3 Standard Assumptions

Unless stated otherwise:

1. All data (\(p_j, r_j, d_j, w_j\)) are non-negative integers.
2. Machines process at most one job at a time.
3. Jobs are non-preemptive (interruption is forbidden) unless β contains “pmtn”.
4. Each job requires exactly one operation on each relevant machine.
5. Setup and teardown times are absorbed into processing times or treated separately via \(s_{jk}\).

Chapter 2: Single-Machine Scheduling

2.1 The Problem \(1 \| \| C_{\max}\)

With a single machine and no side constraints, makespan equals the total processing time regardless of sequence:

This is trivially optimal; every permutation achieves the same makespan.

2.2 Minimising Weighted Completion Time: \(1 \| \| \sum w_j C_j\)

The WSPT rule (also called Smith’s rule) runs in \(O(n \log n)\) time. When all weights are equal (\(w_j = 1\)), WSPT reduces to SPT (Shortest Processing Time first), which minimises \(\sum C_j\).

2.3 Minimising Maximum Lateness: \(1 \| \| L_{\max}\)

With release dates (\(1 \| r_j \| L_{\max}\)), the problem becomes NP-hard in general. However:

2.4 Minimising the Number of Late Jobs: \(1 \| \| \sum U_j\)

For the weighted version \(1 \| \| \sum w_j U_j\), the problem is NP-hard (reduces from PARTITION).

2.5 Minimising Weighted Tardiness: \(1 \| \| \sum w_j T_j\)

This problem is NP-hard (Lawler, 1977; the proof reduces from 3-PARTITION in the strong sense when processing times are arbitrary). For equal weights, \(1 \| \| \sum T_j\) is also NP-hard.

Dynamic programming approach: index jobs by subsets. Let \(f(S)\) = minimum weighted completion time for jobs in set \(S\) scheduled first. The recurrence is:

where \(C_j = p(S)\) (total processing time of \(S\)) if job \(j\) is last in \(S\). This runs in \(O(2^n \cdot n)\) time and \(O(2^n)\) space — exponential but exact.

2.6 Preemptive Scheduling on a Single Machine

The most important preemptive single-machine problems arise when jobs have release dates. Without release dates, preemption never helps for regular objectives (since any non-preemptive schedule can be converted to a preemptive one with the same completion times).

2.7 Precedence Constraints

With precedence constraints (partial order \(\prec\)), the problem \(1 \| \text{prec} \| \sum w_j C_j\) is NP-hard in general. A special case:

Chapter 3: Parallel Machine Scheduling

3.1 Identical Parallel Machines

Makespan: \(P \| \| C_{\max}\)

This problem is NP-hard for \(m \geq 2\) (by reduction from PARTITION; see Chapter 4). Graham’s list scheduling algorithm provides approximation guarantees.

Weighted Completion Time: \(P \| \| \sum w_j C_j\)

The WSPT (Smith’s rule) generalises: schedule jobs globally in non-increasing order of \(w_j / p_j\), breaking ties arbitrarily, then assign each job to the currently least-loaded machine. This is not exactly optimal for \(m \geq 2\) but provides a \(2\)-approximation for the unweighted case and is often near-optimal in practice.

Preemptive Makespan: \(P \| \text{pmtn} \| C_{\max}\)

3.2 Uniform and Unrelated Machines

On uniform machines \(Q \| \| C_{\max}\), machine \(i\) processes job \(j\) in time \(p_j / s_i\). An LP relaxation over job-to-machine assignments can be rounded to yield a \((4/3)\)-approximation.

On unrelated machines \(R \| \| C_{\max}\), processing time \(p_{ij}\) for job \(j\) on machine \(i\) is arbitrary. An LP relaxation (attribute a fraction of job \(j\) to machine \(i\)) rounded by a randomised argument (Lenstra, Shmoys & Tardos, 1990) gives a 2-approximation. This is tight in the sense that no polynomial algorithm achieves ratio \(< 3/2\) unless P = NP.

3.3 Critical Path and Precedence Constraints

For \(P \| \text{prec} \| C_{\max}\) and more generally for project scheduling, the critical path method (CPM/PERT) provides a lower bound:

where the maximum is over all chains in the precedence DAG. When \(m = \infty\) (unlimited machines), the optimal makespan equals this longest path, computable in \(O(n + e)\) time by topological sort (where \(e\) is the number of precedence edges).

3.3b Minimising Weighted Completion Time on Parallel Machines

For \(P||\sum w_j C_j\), the problem is NP-hard in general (by reduction from PARTITION). However, important special cases are tractable.

The reason LRPT works for parallel machines: completing short jobs first on one machine wastes the ability to parallelise. LRPT keeps all machines busy processing the longest remaining jobs simultaneously, reducing the time until all long jobs are done, which paradoxically reduces \(\sum C_j\).

3.4 Bin-Packing Connection

Bin packing: given items of sizes \(s_1, \ldots, s_n \in (0,1]\), pack them into the fewest unit-capacity bins. The problem \(P_m \| \| C_{\max}\) with target \(T^*\) is equivalent to bin packing: can \(n\) jobs of sizes \(p_j / T^*\) be packed into \(m\) bins of capacity 1?

First Fit Decreasing (FFD) uses at most \(11/9 \cdot \mathrm{OPT} + 6/9\) bins (Johnson, 1973). Bin packing has no PTAS for the number-of-bins objective unless P = NP (Karmarkar & Karp, 1982), but for the makespan objective on \(m\) fixed machines, a PTAS exists (see Chapter 8).

Chapter 4: Computational Complexity in Scheduling

4.1 Complexity Classes

4.2 Strong vs. Weak NP-Hardness

Key consequences:

• A strongly NP-hard problem has no FPTAS (fully polynomial-time approximation scheme) unless P = NP.
• A weakly NP-hard problem may admit an FPTAS (scale and round the DP).

4.3 Key Reductions for Scheduling

PARTITION and \(P2 \| \| C_{\max}\)

PARTITION: Given positive integers \(a_1, \ldots, a_n\), does there exist \(S \subseteq [n]\) with \(\sum_{i \in S} a_i = \sum_{i \notin S} a_i\)?

Since the reduction uses exponentially large numbers (the values \(a_i\) can be exponential in the input bit-length), \(P2 \| \| C_{\max}\) is only weakly NP-hard. In fact, an FPTAS exists (via dynamic programming on the DP table for makespan).

3-PARTITION and \(P_m \| \| C_{\max}\) (strongly NP-hard)

3-PARTITION: Given \(3q\) positive integers \(a_1, \ldots, a_{3q}\) with \(B/4 < a_i < B/2\) and \(\sum a_i = qB\), can they be partitioned into \(q\) triples each summing to \(B\)?

NP-hardness of \(1 \| r_j \| \sum C_j\)

Other NP-hardness results

Polynomial-time solvable problems (selected):

Chapter 5: Integer Programming and Exact Methods

5.1 IP Formulations for Single-Machine Problems

Positional (assignment) formulation

Let \(x_{jk} = 1\) if job \(j\) is assigned to position \(k\) in the sequence. Then:

subject to \(\sum_k x_{jk} = 1\) for all \(j\), \(\sum_j x_{jk} = 1\) for all \(k\), \(x_{jk} \in \{0,1\}\), where \(C_{jk} = \sum_{l=1}^{k} \sum_{j'} p_{j'} x_{j'l}\). This is a linear assignment problem when completion times are linear in positions.

Disjunctive (precedence) formulation

Let \(y_{jk} = 1\) if job \(j\) precedes job \(k\). Let \(C_j\) be a continuous completion-time variable. Then \(1 \| \| \sum w_j C_j\) (with sequence-dependent setups \(s_{jk}\)) can be written:

This “big-M” formulation has \(O(n^2)\) binary variables and is the basis for branch-and-bound.

5.1b LP Relaxations and Duality in Scheduling

Linear programming relaxations play a central role in deriving lower bounds and approximation algorithms for scheduling problems. The key insight is that many scheduling problems can be formulated as integer programs whose LP relaxations are both tractable and informative.

The exponentially many constraints (one per subset \(S\)) are handled in practice by a separation oracle: given a candidate solution \((C_j)\), find a violated constraint or certify that none exists. For this particular LP, the separation problem reduces to a sorting problem solvable in \(O(n \log n)\), making the overall LP solvable in polynomial time.

5.2 Connection to the Travelling Salesman Problem

When sequence-dependent setup times \(s_{jk}\) are present, minimising \(C_{\max}\) on one machine is equivalent to finding a Hamiltonian path in the complete graph on \(n+1\) nodes (jobs plus a dummy start node) with edge weights \(s_{jk}\). This is precisely the asymmetric TSP. Conversely, instances of TSP can be encoded as single-machine scheduling problems with sequence-dependent setups, establishing that \(1 \| s_{jk} \| C_{\max}\) is NP-hard.

5.3 Dynamic Programming

Branch-and-bound finds exact solutions by pruning the search tree, but it offers no polynomial-time guarantee — its worst-case complexity is still exponential. Dynamic programming is a different exact method that exploits optimal substructure: if the jobs \(S \setminus \{j\}\) are scheduled optimally and job \(j\) is appended last, the result is an optimal schedule for \(S\) (given that \(j\) is scheduled last). This substructure holds for a wide range of single-machine objectives — including \(\sum w_j T_j\) — because total weighted tardiness decomposes additively over jobs and the contribution of job \(j\) depends only on when it completes.

Two flavors of DP are relevant in scheduling. The exponential-state DP stores one value per subset \(S \subseteq \{1,\ldots,n\}\), giving \(O(2^n \cdot n)\) time — exponential but far better than \(n!\). This is valuable when \(n \leq 20\) or so. The pseudo-polynomial DP applies when the objective has integer data and the problem is only weakly NP-hard: the state space is polynomial in the numeric values of the input (e.g., total processing time), making it practical when those values are small. The FPTAS for \(P2 \| \| C_{\max}\) below is a rounding technique that turns a pseudo-polynomial DP into a fully polynomial approximation scheme.

DP for \(1 \| \| \sum w_j T_j\)

Let \(f(S, t)\) = minimum weighted tardiness of jobs in \(S\) when they are scheduled starting at time \(t\). Then:

Since \(t\) is determined by \(S\) (it equals the total processing time of jobs not in \(S\)), the state space has \(2^n\) entries. Running time: \(O(2^n \cdot n)\).

Pseudo-polynomial DP for weakly NP-hard problems

For \(P2 \| \| C_{\max}\) with integer data: let \(W = \sum_j p_j\). Define \(V[i]\) = 1 if a subset of jobs with total processing time exactly \(i\) exists. Recurrence: \(V[i] = 1\) if \(V[i - p_j] = 1\) for some \(j\). Running time: \(O(nW)\). Optimal makespan: \(\min_{i \leq \lfloor W/2 \rfloor} \{W - i : V[i] = 1\}\). This DP can be scaled to yield an FPTAS for \(P2 \| \| C_{\max}\).

5.4 Branch-and-Bound

Branch-and-bound (B&B) explores the implicit enumeration tree of all schedules, pruning branches whose lower bound exceeds the current best-known upper bound.

Branching strategies:

1. Fix the next job: at each node, branch on which job is assigned to the next open position. Produces a tree of depth \(n\) with \(n!\) leaves.
2. Assign jobs to time slots: branch on which job is processed at a given time on a given machine.

Lower bounds:

• Preemptive relaxation: solve the preemptive version (polynomial) to get a lower bound on the non-preemptive optimum.
• Machine relaxation: allow a job to be processed simultaneously on all machines; the resulting single-machine problem is easier.
• LP relaxation: solve the LP relaxation of the IP formulation; the optimal LP value is a valid lower bound.

Carlier–Pinson algorithm (1989): For \(J \| \| C_{\max}\) (job shop), a sub-problem on the bottleneck machine yields a 1-machine problem; solving this by Jackson’s preemptive schedule and computing its lower bound enables efficient pruning.

Chapter 6: Flow Shops

6.1 Johnson’s Algorithm for \(F_2 \| \| C_{\max}\)

In a 2-machine flow shop, every job \(j\) has a processing time \(p_{j1}\) on machine 1 and \(p_{j2}\) on machine 2, performed in that order.

Why Johnson’s rule works: The exchange argument shows that for any adjacent jobs \(j\) before \(k\), it is never better to swap if \(\min(p_{j1}, p_{k2}) \leq \min(p_{k1}, p_{j2})\). The algorithm constructs a sequence satisfying this pairwise condition for all adjacent pairs.

6.2 The Flow Shop with More Machines: \(F_m \| \| C_{\max}\), \(m \geq 3\)

For \(F_3 \| \| C_{\max}\) with dominant machines (e.g., \(\min_j p_{j2} \geq \max_j p_{j1}\) or \(\min_j p_{j2} \geq \max_j p_{j3}\)), Johnson’s algorithm generalises: define \(a_j = p_{j1} + p_{j2}\), \(b_j = p_{j2} + p_{j3}\) and apply 2-machine Johnson on these combined times.

6.3 Heuristics for Large Flow Shops

NEH heuristic (Nawaz, Enscore & Ham, 1983): one of the best constructive heuristics for \(F_m \| \| C_{\max}\).

6.4 Flexible Flow Shops

A flexible flow shop (hybrid flow shop) has \(s\) stages; at stage \(k\), there are \(m_k \geq 1\) parallel identical machines. Every job must be processed at every stage. This generalises both the flow shop (\(m_k = 1\)) and the parallel machine problem (\(s = 1\)). Minimising \(C_{\max}\) is NP-hard even with \(s = 2\) and \(m_1 = 1\), \(m_2 = 2\).

Chapter 7: Job Shops and Open Shops

7.1 The Job Shop: \(J_m \| \| C_{\max}\)

In a job shop, each job \(j\) has a specific routing: a sequence of machines \(\mu_{j1}, \mu_{j2}, \ldots, \mu_{j n_j}\) (not necessarily all machines) with corresponding processing times. Jobs cannot be preempted.

A trivial lower bound on makespan: \(C_{\max} \geq \max_j \sum_k p_{jk}\) (no job can complete before its total processing) and \(C_{\max} \geq \max_i \sum_j p_{ji}\) (no machine can be overloaded).

7.2 The Disjunctive Graph Model

A complete acyclic orientation of the disjunctive arcs assigns a direction to every disjunctive arc such that the resulting directed graph is acyclic. Each such orientation corresponds to a feasible (non-preemptive) job shop schedule. The makespan equals the length of the longest path from \(s\) to \(t\) in the oriented graph.

7.3 Branch-and-Bound for \(J \| \| C_{\max}\)

The most effective exact algorithms for the job shop use branch-and-bound over the disjunctive graph:

1. Branching: At each node, select an unresolved disjunctive arc (machine conflict). Branch into two sub-problems: one where operation \(u\) precedes \(v\), one where \(v\) precedes \(u\).
2. Lower bound: Compute the longest path in the partially oriented graph. This requires solving a longest-path problem in a DAG: \(O(|V| + |C \cup D'|)\) where \(D'\) is the set of currently oriented disjunctive arcs.
3. Pruning: If the lower bound at any node exceeds the best known solution, prune that branch.

The Carlier–Pinson algorithm (1989) strengthens the lower bound by extracting a single-machine bottleneck subproblem (\(1 \| r_j, q_j \| C_{\max}\) with head/tail times) and solving it exactly — this gives a tighter bound and enables more pruning.

7.4 Open Shops

In an open shop, each job must be processed once on each machine, but the order of machines is unconstrained (can differ per job and can be chosen as part of the optimisation).

For non-preemptive open shops: \(O_2 \| \| C_{\max}\) is solvable in polynomial time (Gonzalez & Sahni), but \(O_m \| \| C_{\max}\) for \(m \geq 3\) is NP-hard (reduction from 3-PARTITION).

Chapter 8: Approximation Algorithms

8.1 Framework and Definitions

8.2 List Scheduling: \(P_m \| \| C_{\max}\)

Recall from Chapter 3:

• List scheduling: \(2 - 1/m\) ratio (Graham, 1969).
• LPT rule: \(4/3 - 1/(3m)\) ratio (Graham, 1969).

The LPT ratio is tight: instances with ratio approaching \(4/3\) exist (e.g., \(m = 3\) machines, 7 jobs with times \(3,3,2,2,2,1,1\)).

8.3 PTAS for \(P_m \| \| C_{\max}\) (Fixed \(m\))

APX-hardness for variable \(m\): When \(m\) is part of the input, \(P \| \| C_{\max}\) is APX-hard (no PTAS unless P = NP), since bin packing (which is APX-hard for the number of bins) reduces to it.

8.4 Approximation for \(R \| \| \sum w_j C_j\)

For unrelated machines with weighted completion time:

1. Formulate an LP relaxation: minimise \(\sum_j w_j \bar{C}_j\) where \(\bar{C}_j\) are fractional completion times obtained by LP. The LP can be solved in polynomial time and its value is at most OPT.
2. Randomised rounding: assign each job \(j\) to machine \(i\) with probability \(x_{ij}\) (from the LP solution), independently. The resulting integer schedule has expected cost at most 2·OPT (Schulz & Skutella, 2002).

This gives a 2-approximation (the integrality gap of the LP is exactly 2).

8.5 Preemptive Lower Bounds and Rounding

A general technique: solve the preemptive relaxation (which is polynomial) to obtain \(C_{\max}^{\text{pmtn}} \leq \mathrm{OPT}_{\text{non-pmtn}}\). Then convert the preemptive schedule to a non-preemptive one. For \(P \| \| C_{\max}\):

(Each job is delayed by at most one preemption-induced gap of size \(\max_j p_j \leq \mathrm{OPT}\).)

More refined analyses give the \((4/3)\)-approximation for LPT.

Chapter 9: Metaheuristics and Practical Procedures

9.1 Local Search

Neighbourhood structure: For permutation scheduling problems (single machine, flow shop), define a neighbourhood \(N(\pi)\) of schedule \(\pi\) as all schedules reachable by one move:

• Swap: interchange jobs at positions \(i\) and \(j\).
• Insert (shift): remove job at position \(i\) and reinsert at position \(j\).
• 2-opt: reverse a sub-sequence between positions \(i\) and \(j\).

Local search algorithm:

1. Start from an initial solution \(\pi_0\) (e.g., from a constructive heuristic).
2. Evaluate all (or a random subset of) neighbours.
3. Move to the best improving neighbour.
4. Terminate when no improving neighbour exists (local optimum).

Local search for \(J \| \| C_{\max}\): the neighbourhood is defined by swapping two adjacent operations on the critical path (the longest path in the disjunctive graph). Only moves on the critical path can improve the makespan, so the effective neighbourhood is small.

9.2 Simulated Annealing

Simulated annealing (Kirkpatrick, Gelatt & Vecchi, 1983) extends local search by occasionally accepting worse solutions to escape local optima.

Under appropriate cooling schedules, simulated annealing converges to a global optimum with probability 1 (Hajek, 1988) — but the required number of iterations is generally exponential. In practice, SA produces near-optimal solutions for \(J \| \| C_{\max}\) in reasonable computation time.

Application to job shop: The neighbourhood consists of single-arc reversals on the critical path (van Laarhoven et al., 1992). Starting from a greedy schedule (e.g., LPT dispatching), SA explores thousands of moves per second and typically finds solutions within 1–2% of the best known lower bound on benchmark instances.

9.3 Tabu Search

Tabu search (Glover, 1986) keeps a tabu list of recently performed moves (or recently visited solutions) and forbids reversing them for a fixed number of iterations (the tabu tenure).

Key features:

• Intensification: once a promising region is found, search more deeply there.
• Diversification: when stuck, make a large random move to unexplored regions.
• Aspiration criterion: accept a tabu move if it produces a solution better than all previously seen solutions.

For \(F_m \| \| C_{\max}\), tabu search on the space of job permutations with insert/swap moves is state-of-the-art (Nowicki & Smutnicki, 1996 for job shop; Taillard, 1990 for flow shop).

9.4 Genetic Algorithms

Genetic algorithms (Holland, 1975) maintain a population of solutions and evolve it via selection, crossover, and mutation.

Encoding for scheduling: A permutation \(\pi\) of jobs represents a schedule (evaluated by a priority rule or constructive decoder). Alternatively, a matrix of machine assignments encodes a parallel machine schedule.

Crossover operators for permutations:

• PMX (Partially Mapped Crossover): select two cut points in parent permutations; copy the middle segment from parent 1; fill remaining positions using the order from parent 2, avoiding duplicates by the mapping defined in the copied segment.
• OX (Order Crossover): copy a sub-sequence from parent 1; fill remaining positions in the order they appear in parent 2.

Mutation: swap two randomly chosen positions in the permutation (or apply a random insert move).

Selection: tournament selection (select \(k\) individuals at random, keep the best) or roulette wheel selection (probability proportional to fitness).

For scheduling, the fitness function is the objective value (\(C_{\max}\), \(\sum w_j C_j\), etc.) after decoding the chromosome to a schedule.

9.4b Iterated Local Search

Iterated local search (ILS) combines local search with a perturbation step to escape local optima repeatedly.

ILS is especially effective for flow shop and job shop scheduling because the double-bridge perturbation is large enough to escape deep local optima but preserves enough structure to allow quick re-optimisation by local search. It consistently outperforms pure local search on benchmark instances (Taillard, 1993) while being much simpler to implement than genetic algorithms.

9.5 Real-World Scheduling Complexity

Practical scheduling instances involve constraints far beyond the standard \(\alpha|\beta|\gamma\) framework:

• Workforce scheduling (e.g., nurse rostering): legal limits on consecutive hours worked, minimum rest periods between shifts, fairness (equitable distribution of undesirable shifts), part-time employees.
• Airline crew rostering: pairing of flights into duty periods, crew legality rules (FAA/EASA regulations), crew qualifications, overnight layovers, bidding and seniority.
• Sports league scheduling: home/away balance, travel distance minimisation, TV broadcast constraints, venue availability, avoiding certain matchups in consecutive rounds.

These problems are typically modelled as integer programmes with hundreds of thousands of variables, or as constraint satisfaction problems (CSP) solved by constraint programming (CP) solvers such as IBM CP Optimizer or Google OR-Tools.

Constraint programming reasons about feasibility through arc consistency and domain propagation, often combined with a branch-and-bound search. For scheduling, CP supports global constraints such as cumulative (machine capacity over time) and no-overlap (non-preemptive scheduling), enabling efficient pruning without explicit enumeration.

Chapter 10: Online and Stochastic Scheduling

10.1 Online Scheduling

In offline scheduling, the algorithm knows all jobs in advance before making any assignment decision. In online scheduling, jobs arrive over time and must be assigned irrevocably upon arrival, without knowledge of future jobs.

10.2 Stochastic Scheduling

In stochastic scheduling, processing times are not deterministic constants but random variables. The scheduler observes job completions and may choose the next job based on past observations (adaptive policy).

The key property enabling SEPT’s optimality for exponential distributions is the memoryless property: the remaining processing time of a job in service is independent of how long it has already been running. This means that the expected completion time of a job is its expected processing time regardless of when we start it, and the WSPT exchange argument carries over directly to the stochastic setting.

Summary Table: Key Results in CO 454

Chapter 11: Mathematical Programming Formulations

Combinatorial scheduling problems admit natural formulations as integer programmes (IPs) or mixed-integer programmes (MIPs). While these formulations are not polynomial-time algorithms, they provide two distinct utilities: they allow optimal solutions to be found by branch-and-bound solvers (CPLEX, Gurobi) for moderate-sized instances, and they are the starting point for LP-relaxation-based approximation algorithms.

11.1 Time-Indexed Formulations

The time-indexed formulation is the most natural IP model for scheduling. Discretise the time horizon into integer slots \(t = 1, 2, \ldots, T\), where \(T = \sum_j p_j\) is an upper bound on the makespan.

The LP relaxation of this formulation (replacing \(x_{jt} \in \{0,1\}\) with \(0 \leq x_{jt} \leq 1\)) has a known integrality gap of at most \(e/(e-1) \approx 1.582\). By rounding the LP solution — assigning each job to the first slot where its fractional completion exceeds 1/2 — one obtains a polynomial-time \((1+\varepsilon)\)-approximation for \(1|r_j|\sum w_j C_j\) (after a careful geometric rounding argument due to Schulz and Skutella). The time-indexed LP is the basis of several state-of-the-art approximation algorithms.

11.2 Disjunctive Programme for the Job Shop

The classical mathematical programming model for job shop scheduling uses disjunctive variables to represent the ordering of jobs on each machine.

The LP relaxation (relaxing \(z_{ijk}\) to \([0,1]\)) has an unbounded integrality gap in general, but branch-and-bound on the disjunctive variables — a technique known as shifting bottleneck when combined with single-machine subproblem solvers — is the dominant exact method for \(J_m||C_{\max}\) in practice.

11.3 Approximation Schemes

For certain NP-hard scheduling problems, a polynomial-time approximation scheme (PTAS) exists: for any fixed \(\varepsilon > 0\), the algorithm runs in time polynomial in \(n\) (though possibly exponential in \(1/\varepsilon\)) and returns a solution within a \((1+\varepsilon)\) factor of optimal.

11.4 Critical Path and the Project Scheduling Perspective

Scheduling with precedence constraints (\(\text{prec}\)) arises naturally in project management. The critical path method (CPM) solves the deterministic project scheduling problem optimally.

The connection to scheduling: CPM solves \(1|\text{prec}|C_{\max}\) in \(O(n+m)\) time (just a longest-path computation). The single-machine problem with general objectives (\(L_{\max}\), \(\sum w_j C_j\)) and precedence constraints is considerably harder. Lawler’s algorithm solves \(1|\text{prec}|L_{\max}\) in \(O(n^2)\); general weighted criteria with precedence are strongly NP-hard.

11.5 Parametric and Sensitivity Analysis

In practice, scheduling decisions are made repeatedly in a changing environment. Sensitivity analysis asks: how much can problem parameters change before the optimal schedule changes? This is dual to standard LP sensitivity analysis.

For the WSPT rule (\(1||\sum w_j C_j\)), the optimal sequence is determined by the ratios \(w_j / p_j\). A perturbation of job \(j\)’s weight by \(\delta\) changes its position in the optimal order only if the perturbed ratio crosses the ratio of an adjacent job in the sequence. Formally, if job \(j\) is optimally scheduled immediately before job \(k\) (so \(w_j/p_j \geq w_k/p_k\)), the ordering remains optimal provided \(w_j / p_j + \delta/p_j \geq w_k/p_k\), i.e., \(\delta \geq p_j(w_k/p_k - w_j/p_j)\). This gives a per-job stability range for the weights.

Chapter 12: Open Problems and Research Frontiers

Several fundamental questions in scheduling theory remain open:

1. Complexity of \(1|r_j|\sum C_j\): This problem (unit-weight completion times with release dates) is NP-hard (weakly), but whether it has a pseudo-polynomial algorithm or is strongly NP-hard is unknown for the preemptive version \(1|r_j, \text{pmtn}|\sum C_j\). The preemptive version is solved by SRPT (polynomial), but the non-preemptive version’s precise complexity is unresolved.

2. Approximation ratio for \(J_m||C_{\max}\): The general job shop has no known constant-factor approximation. The best known algorithms achieve \(O(\log n \log m)\)-approximation via LP rounding on the disjunctive formulation. Closing this gap to a constant-factor approximation (or proving a lower bound) is a major open problem.

3. Online scheduling lower bounds: For online makespan minimisation on \(m\) machines, the best known competitive ratio is between \(1.54\) (lower bound) and \(1.923\) (upper bound) for large \(m\). Closing this gap is open.

4. Stochastic vs. deterministic gaps: For most objectives, the best stochastic scheduling policy is not known in closed form for general (non-exponential) distributions. Understanding how much the optimal expected cost exceeds the optimal deterministic cost (the “price of stochasticity”) in terms of distributional parameters is an active research area.

These questions connect scheduling to broader themes in computational complexity, approximation algorithms, and probability theory. The field remains one of the most mathematically rich and practically relevant areas of combinatorial optimisation.

Appendix: Reduction Templates for Scheduling NP-Hardness Proofs

Most NP-hardness reductions for scheduling follow one of three templates, each translating a known NP-hard problem into a scheduling instance.

Template 1: Reduction from PARTITION. To prove \(P_2||C_{\max}\) is weakly NP-hard, reduce from PARTITION: given integers \(a_1, \ldots, a_n\) with \(\sum a_i = 2B\), construct jobs with \(p_j = a_j\) on two machines and ask if \(C_{\max} \leq B\). A perfect partition corresponds to a balanced schedule. This template yields weak NP-hardness (the problem is polynomial when processing times are bounded polynomially in \(n\)).

Template 2: Reduction from 3-PARTITION. To prove strong NP-hardness, reduce from 3-PARTITION (NP-hard in the strong sense): given \(3m\) integers \(a_i \in (B/4, B/2)\) summing to \(mB\), ask if they partition into \(m\) triples each summing to \(B\). Construct \(m+1\) jobs per “slot” such that each machine in the schedule must fit exactly 3 jobs per unit of time. This template yields strong NP-hardness — no pseudo-polynomial algorithm exists unless P = NP.

Template 3: Reduction from DIRECTED HAMILTONIAN PATH. To prove NP-hardness of problems with precedence constraints (e.g., \(1|\text{prec}|\sum w_j C_j\)), construct a job for each arc and node of the Hamiltonian instance. Precedence constraints encode the graph structure; the optimal schedule corresponds to a Hamiltonian path. This gives NP-hardness in the ordinary sense (since Hamiltonian path is NP-complete but not known to be NP-hard in the strong sense).