Local Search Algorithms for the Oven Scheduling Problem

Abstract

The Oven Scheduling Problem is an NP-hard real-world parallel batch problem arising in electronic component manufacturing. The goal of this problem is to schedule jobs on ovens while minimizing total oven runtime, job tardiness, and setup costs. To reduce oven runtime, compatible jobs can be processed simultaneously in batches. Schedules must respect oven eligibility and availability, job release dates, setup times between batches, and oven capacity constraints, as well as compatibility of job processing times and attributes. We propose and fine-tune a set of local search-based methods including Simulated Annealing, Late Acceptance Hill Climbing, and Tabu Search. A comparative analysis with solutions obtained by exact methods demonstrates the robustness of local search-based methods. We are capable of finding optimal solutions whenever the optimum is known and significantly improve the solution quality for more than half of the instances. The best local search approaches find high-quality solutions within a short amount of time (i.e., already in 30 seconds) which demonstrates their effectiveness for real-world applications.