Abstract: With the rapid increase of the labor cost, more and more companies prefer to hire on-call employees. This paper investigates a new task assignment problem from a home improvement company in China. In this problem, each task is composed of multiple sub-tasks and the assignment takes the personnel training and service time of customers into account. The objective of this problem is to maximize the weighted combination of the number of assigned tasks and the total profit. To solve this problem, we build an integer programming model and design a highly effective local branching algorithm. In addition, we analyze how the different branching variables and parameter settings impact the behavior of the algorithm and determine the best parameter settings. In particular, we observe that the effective selection of local branching variables is dependent on the problem instances. Experimental results disclose that our proposed local branching algorithm is able to obtain better solutions than the general purpose Gurobi solver in competitive computational time.

Key words: task assignment, matheuristics, local branching, integer programming

摘要： 随着劳动力成本的快速增长,越来越多的企业选择雇佣兼职员工。本文研究了中国一家家居企业的任务指派问题,该任务指派问题的特点是一个任务由多个子任务组成,并在安排时需要同时考虑人员培训和满足客户的服务时间的要求,该问题的目标是安排尽可能多的家装任务并获得尽可能多的收益。为了解决该问题,本文建立了整数规划模型,并设计高效的局部分支算法对模型进行求解。为了获得最佳的求解效果,我们实验分析了不同的分支变量和参数设置对算法性能的影响,并获得了最佳的参数设置。特别的,我们发现有效分支变量的选择与问题特点相关。实验还表明,在相同求解时间内,在13个算例中,局部分支算法在9个算例上的表现优于Gurobi。

关键词: 任务指派, 数学启发式, 局部分支算法, 整数规划