Abstract:

In this paper, we introduce the separable task assignment problem (STAP) in which n separable tasks are assigned tom agents subject to agents’ capacity constraints. The objective is to minimize the costs that occur during the manufacturing and the communication between agents.Atask is separable if it can be divided into two pieces, and both of them can be assigned individually or together to any agents. A separable task is considered as being assigned if and only if its two pieces are both assigned. Since several discrete (ternary) variables may be involved in STAP modeling, computing the problem in a reasonable time period is not an easy work. We replace the ternary variables by binary and continuous variables through extending the logarithmic method introduced by Li et al. (INFORMS J Comput 25(4): 643–653, 2012) and Vielma et al.(Oper Res 58(2): 303–315, 2010). Our numerical experiments demonstrate that the newly generated model performs well in solving difficult separable task-assignment problems for pretty large scale of instance sizes.