We introduce and study a parallel machine scheduling problem with almost periodic maintenance activities. We say that the maintenance of a machine is ϵ-almost periodic if the difference of the time between any two consecutive maintenance activities of the machine is within ϵ. The objective is to minimize the makespan Cmax, i.e., the completion time of the last finished maintenance. Suppose the minimum and maximum maintenance spacing are T and T′ = T + ϵ, respectively, then our problem can be described as Pm, M S[T,T′]‖Cmax. We show that this problem is NP-hard, and unless P = N P, there is no polynomial time ρ-approximation algorithm for this problem for any ρ<2. Then we propose a polynomial time 2T′/T-approximation algorithm named BFD-LPT to solve the problem. Thus, if T′ = T, BFD-LPT algorithm is the best possible approximation algorithm. Furthermore, if the total processing time of the jobs is larger than 2m(T′ + TM) and min{pi}⩾T, where TM is the amount of time needed to perform one maintenance activity, then the makespan derived from BFD-LPT algorithm is no more than 3/2 that of the optimal makespan. Finally, we show that the BFD-LPT algorithm has an asymptotic worst-case bound of 1 + σ/(1 + 2σ) if min{pi}⩾T, where σ = TM/T′.
