Name
Abstract | ||
|---|---|---|
In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+驴)p], where p0 and $\phi=(\sqrt{5}-1)/2$ . Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio $(\sqrt{5}+1)/2$ are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio $(\sqrt{5}+1)/2$ . The two class of algorithms are optimal for the problems studied here. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s10878-010-9298-6 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Batching,Scheduling,On-line algorithm,Delivery time | Batch machine,Scheduling (computing),Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 2 | 1382-6905 |
Citations | PageRank | References |
4 | 0.49 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Fang | 1 | 4 | 0.49 |
| Peihai Liu | 2 | 52 | 6.01 |
| Xiwen Lu | 3 | 182 | 21.03 |