Name
Abstract | ||
|---|---|---|
We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2011.06.011 | Theoretical Computer Science |
Keywords | DocType | Volume |
Online algorithm,Batch scheduling,Parallel machines,Delivery time | Journal | 412 |
Issue | ISSN | Citations |
39 | 0304-3975 | 5 |
PageRank | References | Authors |
0.50 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Fang | 1 | 5 | 0.50 |
| Xiwen Lu | 2 | 182 | 21.03 |
| Peihai Liu | 3 | 52 | 6.01 |