Minimizing total completion time on a single machine with a flexible maintenance activity

A problem of jointly scheduling multiple jobs and a single maintenance activity on a single machine with the objective of minimizing total completion time is considered in this paper. It is assumed that the machine should be stopped for maintenance which takes a constant duration within a predefined period. The problem is generalized from the one with a fixed maintenance in that it relaxes the starting time of the maintenance from a fixed time point to a predefined period. Both resumable and nonresumable cases are studied. First, three properties of an optimal solution to each of the two cases are identified. Then it is shown that the proposed shortest processing time (SPT) algorithm is optimal for the resumable case. As for the nonresumable case, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, it is shown that relaxing the starting time of the maintenance cannot improve the relative error bound of the SPT algorithm. The focus of the paper is presented afterwards, which is to develop a dynamic programming algorithm and a branch-and-bound algorithm to generate an optimal solution for this case. Experimental results show that these algorithms are effective and complementary in dealing with different instances of the problem. Statement of scope and purpose: In the majority of scheduling problems with preventive maintenance, maintenance periods are assumed to be constant. However, in real industry settings, such periods may be flexible. Therefore, it is necessary to consider scheduling problems with flexible maintenance. This paper focuses on a single machine problem in which job processing and machine maintenance have to be scheduled simultaneously. The objective is to minimize total completion time of jobs for both resumable and nonresumable cases. For the resumable case, a SPT algorithm proposed in this paper is shown to be optimal. On the other hand, for the nonresumable case, the relative worst-case error bound of the SPT algorithm is analyzed, and further, a dynamic programming algorithm and a branch-and-bound algorithm are proposed to solve this problem optimally. Finally, experimental results are provided to show the effectiveness and complementarity of the above algorithms. © 2010 Elsevier Ltd. All rights reserved.