Parallel-machine scheduling with machine-dependent maintenance periodic recycles

Parallel machine structure is very common in modern production systems. Its performance sometimes has a decisive impact on the whole productivity. In this paper, we consider a parallel-machine scheduling problem where each machine is subject to periodic maintenance. Instead of assuming all the machines have the same maintenance periodic cycle, we assume the maintenance periodic cycles are machine-dependent. The objective is to schedule all the jobs to the machines such that the makespan is minimized. We first provide computational complexity and non-approximability analyses of the problem and then present two mathematical programming models to tackle small-sized instances. Thereafter, we present a worst-case analysis of the classical LPT and LS algorithms for the problem. Then we propose two improved heuristic algorithms based on some observations of large-sized instances. In order to evaluate the performance of the heuristic algorithms, we resort to a lower bound of the optimal makespan, and find that it has a very interesting characteristic. Numerical experiments show that the improved heuristic algorithm MLPT improves the objective value of the LPT schedule by about 6.75% on average and that the MLPT heuristic algorithm has an average-case relative error less than 1.57% for all combinations of instances, which means that it is very suitable for real world applications.