A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems

作者：Li Han Lin^*; Huang Yao Huei; Fang Shu Cherng

来源：INFORMS Journal on Computing, 2013, 25(4): 643-653.

DOI：10.1287/ijoc.1120.0527

• task assignment problem
• binary variables
• mixed-integer programming problem

This paper studies the classical task assignment problem (TAP) in which M unbreakable tasks are assigned to N agents with the objective to minimize the communication and process costs subject to each agent%26apos;s capacity constraint. Because a large-size TAP involves many binary variables, most, if not all, traditional methods experience the difficulty in solving the problem within a reasonable time period. Recent works present a logarithmic approach to reduce the number of binary variables in problems with mixed-integer variables. This study proposes a new logarithmic method that significantly reduces the numbers of binary variables and inequality constraints in solving task assignment problems. Our numerical experiments demonstrate that the proposed method is superior to other known methods of this kind for solving large-size TAPs.

• 出版日期2013