Name
Abstract | ||
|---|---|---|
Batch resource allocation problem arises in the context of executing a sequence of automated system tests or distributed computations where resources are pooled together and flexibly matched with requests. Minimizing resource allocation for a batch of processes reduces the resource management (e.g., setup) cost for the batch while allowing more users to share the resource pool simultaneously. The salient characteristic of the batch resource allocation problem is that while resources can be reused across different processes they are subject to mutually exclusive use for any individual process. We show that resource allocation for a single process can be solved in polynomial time whereas the general optimization problem is NP-complete. This motivates us to consider heuristics that can yield close to optimum solutions in polynomial time. We design several such heuristics and present their experimental comparison. Our experiments show that a technique based on a min-cost max-flow algorithm combined with ranked removal yields the best solution while having smallest running time. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICST.2009.25 | ICST |
Keywords | Field | DocType |
individual process,resource pool,resource allocation,minimizing resource allocation,batch resource allocation problem,polynomial time,optimal resource allocation,different process,batch testing,general optimization problem,resource management,single process,protocols,np complete problem,data mining,distributed system,polynomials,distributed computing,probability density function,testing,optimization problem,resource manager,automation,software testing,system testing | Resource management,Mathematical optimization,Polynomial,Ranking,Computer science,Resource allocation (computer),Real-time computing,Heuristics,Resource allocation,Time complexity,Optimization problem,Distributed computing | Conference |
Citations | PageRank | References |
3 | 0.62 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fangzhe Chang | 1 | 248 | 15.32 |
| Jennifer Ren | 2 | 3 | 0.62 |
| Ramesh Viswanathan | 3 | 278 | 23.10 |