Title | ||
---|---|---|
A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines. |
Abstract | ||
---|---|---|
This paper studies a multi-agent scheduling problem on two identical parallel machines. There are agents, and each agent’s objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than for the th completed agent. Moreover, we show that the performance ratio is tight. |
Year | DOI | Venue |
---|---|---|
2016 | https://doi.org/10.1007/s10951-015-0460-y | J. Scheduling |
Keywords | Field | DocType |
Multi-agent scheduling,Identical machines,Makespan,Approximation algorithm,Performance ratio vector | Approximation algorithm,Mathematical optimization,Job shop scheduling,Computer science,Scheduling (computing),Performance ratio,Real-time computing,Johnson's rule | Journal |
Volume | Issue | ISSN |
19 | 1 | 1094-6136 |
Citations | PageRank | References |
3 | 0.39 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kejun Zhao | 1 | 17 | 2.02 |
Xiwen Lu | 2 | 182 | 21.03 |
Manzhan Gu | 3 | 36 | 4.99 |