Sy. Chang et Hc. Hwang, The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines, DISCR APP M, 92(2-3), 1999, pp. 135-147
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.