Name
Title | ||
|---|---|---|
A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines |
Abstract | ||
|---|---|---|
We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than $1+(\sqrt{m^{2}+4}-m)/2$ , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10951-009-0154-4 | J. Scheduling |
Keywords | Field | DocType |
Scheduling,Parallel Batch Machines,On-line | Mathematical optimization,Job shop scheduling,Computer science,Scheduling (computing),Algorithm,Real-time computing,Batch processing machine,Competitive analysis | Journal |
Volume | Issue | ISSN |
15 | 1 | 1094-6136 |
Citations | PageRank | References |
18 | 1.00 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peihai Liu | 1 | 52 | 6.01 |
| Xiwen Lu | 2 | 182 | 21.03 |
| Yang Fang | 3 | 18 | 1.00 |