Name
Title | ||
|---|---|---|
Dynamic Generalized Assignment Problems with Stochastic Demands and Multiple Agent-Task Relationships |
Abstract | ||
|---|---|---|
The assignment problem is a well-known operations research model. Its various extensions have been applied to the design of distributed computer systems, job assignment in telecommunication networks, and solving diverse location, truck routing and job shop scheduling problems.This paper focuses on a dynamic generalization of the assignment problem where each task consists of a number of units to be performed by an agent or by a limited number of agents at a time. Demands for the task units are stochastic. Costs are incurred when an agent performs a task or a group of tasks and when there is a surplus or shortage of the task units with respect to their demands. We prove that this stochastic, continuous-time generalized assignment problem is strongly NP-hard, and reduce it to a number of classical, deterministic assignment problems stated at discrete time points. On this basis, a pseudo-polynomial time combinatorial algorithm is derived to approximate the solution, which converges to the global optimum as the distance between the consecutive time points decreases. Lower bound and complexity estimates for solving the problem and its special cases are found. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s10898-004-4273-3 | J. Global Optimization |
Keywords | Field | DocType |
job shop scheduling problem,continuous-time generalized assignment problem,consecutive time points decrease,multiple agent-task relationships,dynamic generalized assignment problems,deterministic assignment problem,task unit,pseudo-polynomial time combinatorial algorithm,stochastic demands,assignment problem,job assignment,discrete time point,limited number,generalized assignment problem,operations research | Weapon target assignment problem,Mathematical optimization,Job shop scheduling,Quadratic assignment problem,Deadline-monotonic scheduling,Generalized assignment problem,Assignment problem,Knapsack problem,Linear bottleneck assignment problem,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 1573-2916 |
Citations | PageRank | References |
3 | 0.39 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantin Kogan | 1 | 111 | 21.91 |
| Eugene Khmelnitsky | 2 | 56 | 9.51 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |