Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan

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 CmaxCmax, i.e., the completion time of the last finished maintenance. Suppose the minimum and maximum maintenance spacing are T   and T′=T+ɛT′=T+ɛ, respectively, then our problem can be described as Pm,MS[T,T′]||CmaxPm,MS[T,T′]||Cmax. We show that this problem is NP  -hard, and unless P=NPP=NP, there is no polynomial time ρρ-approximation algorithm for this problem for any ρ<2ρ<2. Then we propose a polynomial time 2T′/T2T′/T-approximation algorithm named BFD-LPT to solve the problem. Thus, if T′=TT′=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)2m(T′+TM) and min{pi}⩾Tmin{pi}⩾T, where TMTM is the amount of time needed to perform one maintenance activity, then the makespan derived from BFD-LPT algorithm is no more than 32 that of the optimal makespan. Finally, we show that the BFD-LPT algorithm has an asymptotic worst-case bound of 1+σ/(1+2σ)1+σ/(1+2σ) if min{pi}⩾Tmin{pi}⩾T, where σ=TM/T′σ=TM/T′.