Scheduling jobs with service level requirements on parallel machines under availability and eligibility constraints

In this paper we consider the problem of scheduling n jobs with service level requirements on m identical machines in the presence of machine availability and availability interval eligibility constraints for minimizing makespan. Each availability interval of machines has a specific service level, and each job has to be processed at availability intervals with the service level specified or higher one. We find that all availability interval eligibility sets of jobs and job sets are nested under this machine scheduling problem. Based on the nesting characteristic, we develop a LFJ-based (Least Flexible Job first) polynomial time algorithm and prove the algorithm is optimal when the processing times of all jobs are equal. Finally, we also show that the complexity of this polynomial algorithm is O(n³), where n denotes the total number of jobs.