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).