A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

We consider the problem of preemptively scheduling nn independent jobs on mm parallel machines so as to minimize the makespan. Each job JjJj has a release time rjrj and it can only be processed on a subset of machines MjMj. The machines are linearly ordered. Each job JjJj has a machine index ajaj such that Mj={Maj,Maj+1,…,Mm}Mj={Maj,Maj+1,…,Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O(nklogP+mnk2+m3k)O(nklogP+mnk2+m3k), where kk is the number of distinct release times and PP is the total processing time of all jobs.