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 m machines, which match the competitive ratio of the current best algorithm when m = 4 , 5 , 6 , are obtained in this paper. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.orl.2015.07.002 | Operations Research Letters |
Keywords | Field | DocType |
Scheduling,Online,Competitive ratio,Lower bound | Online algorithm,Mathematical optimization,Combinatorics,Job shop scheduling,Machine scheduling,Scheduling (computing),Upper and lower bounds,Infimum and supremum,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
43 | 5 | 0167-6377 |
Citations | PageRank | References |
2 | 0.40 | 4 |
Authors | ||
2 |