Exact performance of MULTIFIT for nonsimultaneous machines

This paper considers the problem of assigning n independent jobs to m identical parallel machines with nonsimultaneous starting times. The algorithm MULTIFIT has been applied for the problem but its tight worst-case performance ratio has been unknown. In this paper we prove that the exact performanc...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-04, Vol.167, p.172-187
Main Authors: Hwang, Hark-Chin, Lim, Kyungkuk
Format: Article
Language:English
Subjects:
Algorithms
Mathematical analysis
MULTIFIT
Nonsimultaneous parallel machine scheduling
Worst-case performance ratio
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the problem of assigning n independent jobs to m identical parallel machines with nonsimultaneous starting times. The algorithm MULTIFIT has been applied for the problem but its tight worst-case performance ratio has been unknown. In this paper we prove that the exact performance ratio of MULTIFIT is 2419.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2013.10.022