Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates

This paper addresses the production scheduling problem on a single machine with flexible periodic preventive maintenances (PM), where jobs' release dates are also considered. Both resumable and non-resumable cases are studied. For the resumable case, it is proved that the problem can be solved in polynomial time with Earliest Release Date (ERD) rule. For the non-resumable case, it is proved to be NP-Hard in strong sense. And, a mixed integer programming (MIP) mathematical model is provided. Then, an effective heuristic ERD-LPT based on the properties of optimal solution is proposed. Meanwhile, a branch-and-bound algorithm (B and B) that utilizes several dominance rules is developed to search the optimal schedule for small-to-medium sized problems. Computational results indicate that the proposed heuristic is highly accurate and the two algorithms are complementary in dealing with different sized problems. Furthermore, the improvement of the integration between production scheduling and PM is significant compared with the First-in-First-out (FIFO) rule which is adopted commonly in industry.