The single machine scheduling problem is foundational to the study of production scheduling in general. This article describes four basic problems and their solution methods: total weighted completion time, maximum of nondecreasing cost functions (which includes the maximum lateness problem and the problem with precedence constraints), weighted number of tardy jobs, and total weighted tardiness. Additional problems considered include those with both earliness and tardiness penalties, and those with release dates and preemptions.
