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 epsilon-almost periodic if the difference of the time between any two consecutive maintenance activities of the machine is within E. The objective is to minimize the makespan C-max, i.e., the completion time of the last finished maintenance. Suppose the minimum and maximum maintenance spacing are T and T' = T + 6, respectively, then our problem can be described as Pm, MS[T,T']parallel to C-max. We show that this problem is NP-hard, and unless P = NP, there is no polynomial time rho-approximation algorithm for this problem for any rho < 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' + T-M) and min{p(i}) >= 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 I + sigma/(1 + 2a) if min{p(i)} >= T, where sigma = T-M/T'. (C) 2006 Elsevier Ltd. All rights reserved.