Dynamic Generalized Assignment Problems with Stochastic Demands and Multiple Agent--Task Relationships

Konstantin Kogan, Eugene Khmelnitsky () and Toshihide Ibaraki

Journal of Global Optimization, 2005, vol. 31, issue 1, 17-43

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. Copyright Springer Science+Business Media New York 2005

Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-004-4273-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:31:y:2005:i:1:p:17-43

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-004-4273-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().