Name
Title | ||
|---|---|---|
Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan |
Abstract | ||
|---|---|---|
A two-agent scheduling problem on parallel machines is considered. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. When the number of machines, denoted by , is chosen arbitrarily, we provide an algorithm with performance ratio , i.e., the makespan for agent A given by the algorithm is no more than times the optimal value, while the makespan for agent B is no more than times the threshold value. This ratio is proved to be tight. Moreover, when , we present an algorithm with performance ratio which is smaller than . The ratio is weakly tight. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-014-9744-y | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Two-agent scheduling,Parallel machines,Makespan,Approximation algorithm | Approximation algorithm,Mathematical optimization,Combinatorics,Job shop scheduling,Approx,Upper and lower bounds,Performance ratio,Scheduling (computing),Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 1382-6905 |
Citations | PageRank | References |
3 | 0.40 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kejun Zhao | 1 | 17 | 2.02 |
| Xiwen Lu | 2 | 182 | 21.03 |