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

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

0.00 Avg rating0 Votes
Article ID: iaor20001495
Country: Netherlands
Volume: 92
Issue: 2/3
Start Page Number: 135
End Page Number: 147
Publication Date: Jun 1999
Journal: Discrete Applied Mathematics
Authors: ,
Abstract:

In this paper we consider the nonsimultaneous multiprocessor scheduling problem, or NMSP for short. The NMSP is a makespan minimization scheduling problem which involves the non-pre-emptive assignment of independent jobs on m parallel machines with different starting times. It is well known that the longest 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 optimum makespan, respectively. In this paper, we show that the best known worst-case performance bound, 4/3 of the MLPT, is tight by constructing a worst-case example. Then, we employ the bin-packing heuristic algorithm called the MULTIFIT to solve the NMSP and show that the makespan of the schedule generated by the MULTIFIT algorithm is bounded by 9/7 + 2−k times the optimum 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 question.

Reviews

Required fields are marked *. Your email address will not be published.