Optimal Scheduling for a Single Machine with Preventive Maintenance to Minimize Makespan

Industry 4.0 automation has increased production capacity and line efficiency; however, sustaining these gains depends on effective preventive maintenance to reduce unexpected failures, stabilize production, and avoid schedule disruptions and unnecessary costs. Unlike most prior frameworks that assume continuous machine availability, this study investigated a single-machine scheduling problem that incorporates nonresumable jobs, job release times, and a preventive-maintenance interval. We formulated the problem as a mixed-integer program (MIP) and developed a tailored branch-and-bound algorithm that exploits the structural characteristics of both the maintenance procedures and jobs. While the MIP model is unable to reach optimality for medium-to-large instances [Formula: see text] within 3600[Formula: see text]s, the proposed branch-and-bound method consistently attained optimal makespan solutions for instances with up to 50 jobs, averaging [Formula: see text][Formula: see text]s per instance.