5. Conclusions
This paper investigates single-machine scheduling problems with both aging effect, which is dominated by the processing speed of the machine, and deteriorating maintenance activities. We consider the model where the processing speed of the machine is a decreasing function of its uninterrupted running time. In addition, we assume the machine is subject to at most one maintenance activity during the scheduling horizon, and the maintenance duration is a general function of its start time. The objective is to find jointly the optimal location of the maintenance operation and the optimal job sequence to minimize the makespan and the total completion times. We prove the two problems under study are both NP-complete, and each of them has an optimal sequence subject to S-S rule. Taking the total completion times minimization problem as an example, we devise two DP algorithms to solve the problem with an optimal sequence subject to S-S rule. Furthermore, we analyze the computation complexity of the two algorithms, and show that the problem can be solved in polynomial time if the normal processing times of all jobs are uniformly bounded.
