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

Citation
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
Citations number
5
Categorie Soggetti
Engineering Mathematics
Volume
92
Issue
2-3
Year of publication
1999
Pages
135 - 147
Database
ISI
SICI code
Abstract
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.