What question did this study set out to answer?

To investigate a single-machine scheduling problem incorporating preventive maintenance and job constraints.

March 8, 2026

Optimal scheduling for a single machine with preventive maintenance to minimize makespan

LLLu-Wen Liao TCTsang-Chuan Chang YCYen-Chia Chen

Key Points

To investigate a single-machine scheduling problem incorporating preventive maintenance and job constraints.
Formulated the scheduling problem as a mixed-integer program (MIP)
Developed a branch-and-bound algorithm to solve the MIP
Incorporated non-resumable jobs and job release times into the framework.
MIP model did not achieve optimality for medium-to-large job instances (≥ 20) within the time limit
Branch-and-bound method attained optimal makespan solutions for instances with up to 50 jobs
Average solving time was less than 0.05 seconds per instance.

Abstract

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 non-resumable 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 (≥ 20 jobs) within 3600 s, the proposed branch-and-bound method consistently attained optimal makespan solutions for instances with up to 50 jobs, averaging < 0.05 s per instance.

KI fragen

Bookmark

View Full Paper