Name
Title | ||
|---|---|---|
An algorithm for multi-agent scheduling to minimize the makespan on <Emphasis Type="Italic">m</Emphasis> parallel machines |
Abstract | ||
|---|---|---|
This paper considers a multi-agent scheduling problem, in which each agent has a set of non-preemptive jobs, and jobs of all agents are to be processed on m identical parallel machines. The objective is to find a schedule to minimize the makespan of each agent. For an agent, the definition of \(\alpha \) point is introduced, based on which an approximation algorithm is proposed for the problem. In the obtained schedule, the agent with the ith smallest \(\alpha \) point value is the ith completed agent, and the agent’s completion time is at most \(i+ \left( \frac{1}{3}-\frac{1}{3m}\right) \) times its minimum makespan. Finally, we show the performance analysis is tight. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10951-017-0546-9 | Journal of Scheduling |
Keywords | Field | DocType |
Scheduling, Multi-agent, LPT, Makespan | Approximation algorithm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Computer science,Real-time computing | Journal |
Volume | Issue | ISSN |
21 | 5 | 1099-1425 |
Citations | PageRank | References |
2 | 0.37 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manzhan Gu | 1 | 36 | 4.99 |
| Jinwei Gu | 2 | 687 | 39.49 |
| Xiwen Lu | 3 | 182 | 21.03 |