Single-machine scheduling

Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on a single machine, in a way that optimizes a certain objective, such as the throughput.

Single-machine scheduling is a special case of identical-machines scheduling, which is itself a special case of optimal job scheduling. Many problems, which are NP-hard in general, can be solved in polynomial time in the single-machine case.^{[1]: 10–20}

In the standard three-field notation for optimal job scheduling problems, the single-machine variant is denoted by 1 in the first field. For example, " 1||${\displaystyle \sum C_{j}}$" is a single-machine scheduling problem with no constraints, where the goal is to minimize the sum of completion times.

The makespan-minimization problem 1||${\displaystyle C_{\max }}$, which is a common objective with multiple machines, is trivial with a single machine, since the makespan is always identical. Therefore, other objectives have been studied.^[2]