Parallel machines scheduling with nonsimultaneous machine available time (Q757232)

A generalization of the known m parallel identical machines non- preemptive scheduling problem in which the object is to minimize the makespan (the total completion time) is considered. The difference to other approaches consists in the presence of release times for the machines, i.e. for every machine \(m_ i\) the earliest time \(a_ i\) that the machine can start to process the jobs is given. Two approximate algorithms are proposed. The following results are obtained. Denote by M and \(M^*\) the makespan for approximate and optimal schedule respectively. Then for the known LPT algorithm (the longest processing time) the relationship \(M\leq ((3/2)-(1/2m))M^*\) holds. For a modification of the LPT algorithm the author obtained \(M\leq 4M^*/3\). The time complexity of the algorithms is O(n log n\(+n \log m)\) and \(O((n+m)\log (n+m)+(n+m)m)\) respectively. As shown, the performance guarantee for the LPT algorithm is tight, i.e. a sample of the problem exists where \(M=((3/2)+(1/2m))M^*\).