Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418778 | Discrete Applied Mathematics | 2014 | 16 Pages |
Abstract
This paper considers the problem of assigning nn independent jobs to mm 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hark-Chin Hwang, Kyungkuk Lim,