Contents

Single Machine SchedulingEdit

Single machine scheduling (SMS) is a foundational topic in operations research and production planning. It studies how to arrange a set of jobs that must be processed on a single machine in some order, with the goal of optimizing one or more performance measures. Each job j carries a processing time p_j, and additional attributes may include release dates r_j (when a job becomes available), due dates d_j (when a job should ideally be completed), and weights w_j (priority or penalty associated with the job). A schedule specifies the order in which jobs are processed, and C_j denotes the completion time of job j. Depending on the application, objectives can focus on throughput, responsiveness, or resource utilization. In mathematical terms, SMS is often described using Graham’s notation, such as 1|r_j|C_max or 1||∑ w_j C_j, which helps categorize problems by the presence of release dates and the chosen objective. The field spans exact algorithms, heuristics, and approximations, reflecting a balance between theoretical tractability and practical usefulness. SMS has broad applicability to manufacturing lines, service operations, and computer systems where a single resource must handle competing tasks, including general CPU scheduling problems and various forms of production planning.

Formalization and notation

  • Basic model: A set J of n jobs, with each job j having processing time p_j. The machine can handle one job at a time, and once a job starts, it must run to completion before the next job begins (non-preemptive in the standard SMS framework). When releases are allowed, a job cannot start before r_j.
  • Schedule and timing: A permutation π of the jobs defines the processing order. The completion time C_j for job j is the time when j finishes in the schedule. Other time metrics include start times S_j and waiting times W_j.
  • Common notations: The standard way to express SMS instances uses Graham’s notation. For example, 1|r_j|C_max denotes a single machine with release dates aiming to minimize the makespan, while 1||∑ w_j C_j denotes a single machine without release dates aiming to minimize the weighted sum of completion times. See Graham's notation for background on this scheme.
  • Objective categories:
    • Minimize makespan: minimize C_max, the time by which all jobs are finished.
    • Minimize total completion time: minimize ∑ C_j.
    • Minimize weighted completion time: minimize ∑ w_j C_j.
    • Minimize tardiness or lateness: tardiness T_j = max{0, C_j − d_j}, lateness L_j = C_j − d_j, and objectives such as ∑ w_j T_j or max_j L_j.
    • Minimize the number of tardy jobs: ∑ U_j, where U_j indicates whether job j is tardy.
  • Notation remarks: When release dates are present, or when scheduling with setup times or precedence constraints, the problem becomes more complex. For a general overview of hardness and tractability, see NP-hard results in SMS and related discussions in Scheduling theory.

Core results and classic rules

  • Minimizing the sum of completion times (unweighted): The Shortest Processing Time (SPT) rule is optimal. In other words, scheduling jobs in nondecreasing order of p_j minimizes ∑ C_j. This rule is often attributed to the fundamental insight behind Smith’s rule for related objectives. See Shortest processing time and Smith's rule.
  • Minimizing the weighted sum of completion times (no release dates): The Weighted Shortest Processing Time (WSPT) rule applies. Jobs are ordered by p_j/w_j in nondecreasing order, which minimizes ∑ w_j C_j. This rule is a cornerstone result in SMS and is closely connected to the broader idea of Smith’s rule. See Smith's rule and Weighted shortest processing time.
  • Minimizing the maximum lateness with due dates (no release dates): The earliest due date (EDD) rule is optimal for L_max when all jobs are available at time zero. Sorting by increasing due date d_j yields schedules that minimize the maximum lateness. See Earliest due date.
  • Minimizing the makespan with release dates or more complex constraints: In the presence of release dates r_j, the problem 1|r_j|C_max is generally NP-hard, meaning that no polynomial-time algorithm is known for the worst case and practical approaches rely on heuristics or exact methods on smaller instances. See NP-hard and discussions of release-date scheduling.
  • Other objective variants: Problems such as 1||∑ w_j C_j with release dates, or 1|r_j|∑ w_j C_j, are typically harder and commonly addressed with mixed strategies that combine exact techniques (branch-and-bound, dynamic programming for small instances) with heuristics and metaheuristics for larger, realistic instances. See Scheduling theory and Optimization.

Algorithms and heuristics

  • Exact methods: For small to moderate instance sizes, or for special-case structures, exact algorithms based on dynamic programming, branch-and-bound, or integer programming formulations can yield provably optimal schedules. See Dynamic programming and Branch and bound.
  • Heuristics and metaheuristics: Real-world SMS problems typically rely on heuristics due to size and stochasticity. Common approaches include greedy rules (SPT, WSPT, EDD), local search, and metaheuristic methods such as genetic algorithms, tabu search, and simulated annealing. See Heuristics and Metaheuristic methods.
  • Special-case tractability: Some SMS variants with restricted data (e.g., unit processing times p_j = 1, or identical release times) admit polynomial-time solutions or simple optimal policies. See discussions of tractable special cases in Single machine scheduling theory.
  • Extensions that complicate solution methods: Scheduling with setup times, batching, sequence-dependent setup times, or precedence constraints adds layers of difficulty and often requires problem-specific heuristics or decomposition approaches. See setup time and precedence constraints in scheduling.

Applications and extensions

  • Manufacturing and logistics: SMS is directly applicable to assembly lines, job shops with a single bottleneck, and order-fulfillment processes where a single resource must serve tasks in some sequence. See Manufacturing and Operations research applications.
  • Computer systems: In CPU scheduling and other resource-allocation settings, SMS concepts help inform policies for task ordering when a single processing unit is the bottleneck. See CPU scheduling.
  • Service operations: SMS ideas appear in scheduling patient appointments, maintenance tasks, and service centers where a single technician or server is available.
  • Extensions and related problems: Real-world problems often incorporate release dates, due dates, setup times, batching, and stochastic processing times. These extensions are studied under more general scheduling theory and often require hybrid methods combining exact and heuristic techniques. See Scheduling theory and Optimization.

See also