Scheduling jobs under increasing linear machine maintenance time

Although scheduling problems with machine availability have attracted many researchers' attention, most of the past studies are mainly focused on one or several prefixed machine maintenance activities. In this research, we assume that the time needed to perform one maintenance activity is an increasing linear function of the total processing time of the jobs that are processed after the machine's last maintenance activity. We consider two scheduling problems with such maintenance requirement in this paper. The first problem is a parallel machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is between two given positive numbers. The objective is to minimize the maintenance makespan, i.e., the completion time of the last finished maintenance. The second problem is a single machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is fixed and the objective is to minimize the makespan, i.e., the completion time of the last finished job. We propose two approximation algorithms for the considered problems and analyze their performances.