| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142111 | Operations Research Letters | 2015 | 6 Pages |
Abstract
We present pseudo lower bounds for the online scheduling problems on parallel and identical machines, which is the infimum of the competitive ratio of an online algorithm that can be proved by using three lower bounds on the optimum makespan. Pseudo lower bounds for fixed mm machines, which match the competitive ratio of the current best algorithm when m=4,5,6m=4,5,6, are obtained in this paper.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zhiyi Tan, Rongqi Li,