Scheduling

Scheduling is the allocation of jobs to machines or resources over time, with the goal of meeting due dates, minimizing completion time, or maximizing resource utilization. In production and operations, scheduling takes the aggregate plan and the master production schedule and turns them into a detailed sequence of operations on specific machines or work centers. Key performance measures include makespan (completion time of the last job), flow time (time a job spends in the system, including waiting), lateness (C_j - d_j, which can be negative if early), tardiness (max(0, C_j - d_j)), and machine utilization (busy time divided by available time). Scheduling problems are classified using the notation α|β|γ, where α describes the machine environment (single machine, parallel machines, flow shop, job shop, open shop), β describes job characteristics and constraints (processing times, release dates, due dates, precedence, preemption), and γ describes the objective (makespan C_max, total completion time ΣC_j, maximum lateness L_max, total tardiness ΣT_j). For the single-machine case, several rules give optimal solutions for specific objectives: shortest processing time (SPT) minimizes mean flow time and mean completion time; earliest due date (EDD) minimizes maximum lateness; and Moore-Hodgson's algorithm minimizes the number of tardy jobs. The weighted shortest processing time (WSPT) rule orders jobs by decreasing p_j/w_j to minimize weighted completion time. For the two-machine flow shop, Johnson's rule minimizes makespan: jobs are split into two sets depending on whether their first operation is shorter than their second, then sequenced accordingly. The job shop is NP-hard for most objectives, so practical scheduling relies on dispatching rules (SPT, EDD, critical ratio, slack per remaining operation), simulation, and heuristics such as shifting bottleneck or tabu search. Scheduling is further complicated by sequence-dependent setup times, machine breakdowns, operator availability, and material shortages. In practice, schedules must be robust to disruption and are often regenerated periodically or rescheduled in response to real-time events.