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