Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times

We consider a generalized version of the classical parallel machine scheduling problem, in which the m machines are available at time a(j) greater than or equal to 0, j=1, 2, ..., m. The objective function is to maximize the minimum machine completion time. Using the conventional weighting function technique, previously, a lower bound of 5/8 has been shown for the worst-case performance ratio of the famous Longest Processing Timing (LPT) approximation. In this paper, we develop a new method, called matching, and show that the worst-case performance ratio of LPT is exactly (2m − 1)/(3m − 2). We also give an instance to indicate the tightness of this ratio.