Exact Solutions to Task Allocation Problems

Andreas Ernst (), Houyuan Jiang () and Mohan Krishnamoorthy ()
Additional contact information
Andreas Ernst: CSIRO Mathematical and Information Sciences, Private Bag 10, Clayton South MDC, Clayton, VIC 3169, Australia
Houyuan Jiang: Judge Business School, University of Cambridge, Trumpington Street, Cambridge CB2 1AG, United Kingdom
Mohan Krishnamoorthy: CSIRO Mathematical and Information Sciences, Private Bag 10, Clayton South MDC, Clayton, VIC 3169, Australia

Management Science, 2006, vol. 52, issue 10, 1634-1646

Abstract: The task allocation problem (TAP) is one where a number of tasks or modules need to be assigned to a set of processors or machines at minimum overall cost. The overall cost includes the communication cost between tasks that are assigned to different processors and other costs such as the assignment cost and the fixed cost of using processors. Processors may have limited or unlimited capacities to perform tasks. Task allocation has been applied to the design of distributed computing systems and also in auto-manufacturing contexts. We present several integer programs and a column generation formulation for the uncapacitated and the capacitated TAP. Computational experiments are carried out to demonstrate computational capabilities of integer programming and the column generation formulations for the uncapacitated TAP (UTAP). Excellent results are obtained for the column generation formulation. We also report some computational experience for the capacitated TAP (CTAP).

Keywords: task allocation; task assignment; integer programs; column generation (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1060.0578 (application/pdf)

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:inm:ormnsc:v:52:y:2006:i:10:p:1634-1646

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().