The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines

In this paper we consider the nonsimultaneous multiprocessor scheduling pro blem, or NMSP for short. The NMSP is a makespan minimization scheduling pro blem which involves the nonpreemptive assignment of independent jobs on m p arallel machines with different starting times. It is well known that the l ongest processing time (LPT) algorithm and the modified LPT(MLPT) algorithm yield schedules with makespans bounded by 3/2 - 1/2m and 4/3 times the opt imum makespan, respectively. In this paper, we show that the best known wor st-case performance bound, 4/3 of the MLPT, is tight by constructing a wors t-case example. Then, we employ the bin-packing heuristic algorithm called the MULTIFIT to solve the NMSP and shaw that the makespan of the schedule g enerated by the MULTIFIT algorithm is bounded by 9/7 + 2(-k) times the opti mum makespan, where k is the selected number of the major iterations in the MULTIFIT. This worst-case bound of the MULTIFIT algorithm is, so far, the best bound for the NMSP and the tightness of the bound is still an open que stion. (C) 1999 Elsevier Science B.V. All rights reserved.