Single-Machine Scheduling with Fixed Periodic Preventive Maintenance to Minimise the Total Weighted Completion Times

The single-machine scheduling problem with fixed periodic preventive maintenance, in which preventive maintenance is implemented periodically to maintain good machine operational status and decrease the cost caused by sudden machine failure, is studied in this paper. The adopted objective function is to minimise the total weighted completion time, which is representative of the minimisation of the global holding/inventory cost in the system. This problem is proven to be NP-hard; a position-based mixed integer programming model and an efficient heuristic algorithm with local improvement strategy are developed for the total weighted completion time problem. To evaluate the performances of the proposed heuristic algorithms, two new lower bounds are further developed. Computational experiments show that the proposed heuristic can rapidly achieve optimal results for small-sized problems and obtain near-optimal solutions with tight average relative percentage deviation for large-sized problems.