PARALLEL MACHINES SCHEDULING WITH NONSIMULTANEOUS MACHINE AVAILABLE TIME

In this paper we consider the problem of scheduling n independent jobs on m identical machines in order to minimize the makespan, the total finishing time. The jobs are available at time zero, but some machines may not be available at time zero. This problem is a generalization of the classical multiprocessor scheduling problem, where all machines are available simultaneously at time zero. We first show that the makespan obtained by applying the longest processing time (LPT) algorithm to our generalized problem is always within (3/2-1/2m)M* and the bound is tight. We then provide a modified LPT (MLPT) algorithm and show that the makespan obtained by MLPT is bounded by 4/3M*.