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

详细信息    查看全文

• 作者：Wei-Wei Cui^a ; Zhiqiang Lu^b ; ^{zhiqianglu@tongji.edu.cn}
• 关键词：Scheduling ; Preventive maintenance ; Release date ; Makespan
• 刊名：Computers & Operations Research
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：80
• 期：Complete
• 页码：11-22
• 全文大小：1506 K
• 卷排序：80

文摘

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.