What Is Single Machine Scheduling?

Single machine scheduling is a branch of combinatorial optimization concerned with sequencing a set of jobs on one processing resource to minimize one or more performance objectives. It is the foundational model of scheduling theory: all parallel-machine, flow-shop, and job-shop scheduling problems reduce to or generalize from it, making the single-machine case both analytically important and practically relevant for bottleneck analysis in manufacturing, computing, and logistics. The field draws on discrete mathematics, computational complexity theory, and operations research, and its problems are formalized using the three-field Graham notation that specifies machine environment, job characteristics, and optimization criterion.

Each job in the standard model has a processing time, a release date after which it becomes available, and a due date that determines how lateness is measured. The objective function can target makespan (completion time of the last job), total weighted completion time, maximum lateness, number of tardy jobs, or discounted completion times, among many other criteria. Different objectives lead to problems of vastly different computational difficulty, and the choice of criterion is a primary driver of algorithm design.

Scheduling Objectives and Performance Criteria

The most classical single-machine objective is minimizing total weighted completion time, denoted 1 || sum(w_j C_j) in Graham notation. The optimal policy for the unweighted version, 1 || sum(C_j), is the Shortest Processing Time (SPT) rule, which sequences jobs in increasing order of processing time and runs in O(n log n) time. Weighted versions require more care: the Weighted Shortest Processing Time (WSPT) rule, which sequences by decreasing ratio w_j/p_j, is optimal for 1 || sum(w_j C_j) and forms a building block for more constrained variants.

Minimizing maximum lateness, 1 || L_max, is solved optimally by the Earliest Due Date (EDD) rule. When release dates are added, the problem 1 | r_j | L_max becomes NP-hard, as analyzed in the SIAM Journal on Discrete Mathematics treatment of single machine scheduling with release dates, which characterizes complexity boundaries and provides exact algorithms for special cases.

Complexity and Exact Algorithms

Complexity results partition single-machine scheduling problems by their tractability. Problems solvable in polynomial time by priority rules are the easiest class; problems that are NP-hard in the ordinary sense (such as 1 | r_j | sum(w_j C_j)) admit pseudopolynomial dynamic programming algorithms. Strongly NP-hard problems, where no pseudopolynomial algorithm is likely to exist, require exact branch-and-bound methods or integer programming formulations for moderate instance sizes.

Dynamic programming approaches for 1 | r_j | sum(w_j C_j) process jobs in all possible orderings but prune dominated partial schedules. Online scheduling research from Mathematics of Operations Research extends the classical setting to online problems, where jobs arrive over time and must be scheduled without knowledge of future arrivals, providing competitive ratio bounds for greedy and preemptive policies.

Heuristics and Approximation

When exact methods are too slow for large instances, optimization methods such as heuristic sequencing rules, local search, and approximation algorithms provide practical solutions. Approximation algorithms for single-machine problems come with provable performance guarantees expressed as worst-case ratios relative to the optimal objective value. For 1 || sum(w_j C_j) with precedence constraints, list-scheduling heuristics based on topological order achieve approximation ratios within a constant factor of optimal.

Research from the Annals of Operations Research on heuristics for weighted completion time with periodic maintenance illustrates how practical constraints, including machine downtime intervals, are incorporated into heuristic frameworks without abandoning theoretical guarantees.

Applications

Single machine scheduling theory has applications across several engineering and management domains, including:

• Production planning at manufacturing bottleneck workstations, where a single critical machine limits throughput
• Job dispatching in cloud computing clusters, where virtual machine time slots must be allocated to minimize user-perceived latency
• Operating system process scheduling on single-core processors, where CPU time is the shared resource
• Project management for tasks with sequential dependencies and deadline constraints
• Network packet scheduling in routers where a single output link must be shared among competing flows