singlemachine

Single-machine scheduling is a class of optimization problems in operations research and computer science that studies sequencing and timing of jobs processed on a single machine. A set of jobs J = {1, ..., n} each has attributes such as processing time p_j, release date r_j, due date d_j, and weight w_j. A feasible schedule assigns start times s_j and completion times C_j = s_j + p_j, ensuring that no two jobs overlap on the machine and that each job is released before its start (s_j ≥ r_j). In some models, setup times or switching costs between jobs are included.

Common objectives include minimizing makespan C_max (the completion time of the last job), minimizing total completion time Σ C_j, minimizing total weighted completion time Σ w_j C_j, minimizing maximum lateness L_max = max_j (C_j - d_j), and minimizing the number of tardy jobs Σ U_j (U_j ∈ {0,1} indicates tardiness). There are also variants to minimize total tardiness Σ T_j with T_j = max{0, C_j - d_j}.

When there are no release dates, several classic rules give optimal solutions: the shortest processing time first (SPT) rule minimizes Σ C_j; the earliest due date (EDD) rule minimizes L_max; and the weighted version (WSPT) minimizes Σ w_j C_j. For minimizing the number of tardy jobs, Moore's algorithm solves 1||Σ U_j in O(n^2). If preemption is allowed (pmtn), different rules apply and problems such as 1|pmtn|Σ C_j have different optimal policies (e.g., preemption can improve performance for some objectives).

In practice, single-machine scheduling models underpin manufacturing lines, service operations, and computing task schedulers, where the goal is to determine an ordering and timing that meets performance criteria, resource constraints, and deadlines.