Treffer: Exact Solutions to Task Allocation Problems.

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). [ABSTRACT FROM AUTHOR]

Copyright of Management Science is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)