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" 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. 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||formula_1" is an identical machine scheduling problem with no constraints, where the goal is to minimize the sum of completion times. Variants. The makespan-minimization problem 1||formula_2, 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: See also. Many solution techniques have been applied to solving single machine scheduling problems. Some of them are listed below.