Production Scheduling Optimization Using Johnson’s Algorithm at a Food Cannery in Taraba State

Production scheduling efficiency is a determinant of throughput, customer delivery performance, and operational cost in food processing facilities. This study applies Johnson's algorithm and its extensions to optimize the production schedule at a food cannery in Taraba State, North East Nigeria, which processes tomato paste, groundnut paste, and pepper sauce through a sequential two-machine production process. Production order data covering a 12-month operating period are analysed to characterize processing time distributions for each product category across the two machine stages. Johnson's algorithm is applied to determine the optimal sequence of production jobs that minimizes total makespan, defined as the time from commencement of the first job to completion of the last job on the second machine. The optimal sequence is compared against the first-come-first-served and shortest-processing-time schedules currently alternated by the plant scheduler. Results indicate that Johnson's algorithm reduces makespan by 14 percent relative to the current best-performing schedule, translating to approximately 2.3 additional production batches per week. Idle time on the second machine is also reduced by 22 percent. The study extends the analysis to a three-machine environment using Johnson's approximation method, demonstrating further gains when a finishing stage is incorporated. Recommendations include adopting Johnson's algorithm in the daily scheduling process and cross-training operators to reduce inter-stage transfer delays. Keywords: production scheduling, Johnson's algorithm, makespan, food cannery, Taraba State