考虑排班的人力资源投入问题的建模与优化

Modeling and Optimization of Resource Investment Problem Based on Employee-Timetabling

摘要:

结合实际生产或项目中的排班情况，提出考虑排班的人力资源投入问题。针对该问题建立了以最小化人力资源投入为目标的数学模型。根据资源投入量与排班约束的性质，将原问题数学模型简化，证明简化后问题的数学模型与原问题最优解一致，并通过CPLEX软件求解过程,说明简化后的数学模型在求解速度上表现出很大的优越性。对于大规模问题，由于排班约束会导致班次间资源占用，使用传统任务列表编码方式难以获得较优的解。为此,提出了一种新型编码方式的遗传算法。该算法采用对作业延迟时间进行编码的方式，对作业开始时间进行搜索。为了提升算法的局部搜索能力，对作业延迟时间和开始时间进行局部优化。最后，通过数值实验与CPLEX和文献的算法比较，表明该算法的有效性。

Abstract:

In this paper, a resource investment problem is addressed based on employee-timetabling and according to the employee timetabling in practical production systems. A mathematical model aimed at minimizing resource investment is proposed for this problem. In order to solve this problem more efficiently, the mathematical model of the original problem is simplified according to the resource investment and the properties of employee-timetabling constraints. The model proposed is proved to have the same optimal solution as the original mathematical model, and its great advantage in solving speed is verified through the CPLEX software solution process. Meanwhile, for the large-scale problem, as the constraints of employee-timetabling lead to resource occupancy between shifts, it is difficult to obtain a good solution by using the traditional activity list encoding method. A genetic algorithm with a new coding method is designed in this paper, which encodes the job delay time to search the starting time of the job. Moreover, two local optimization methods are proposed which can optimize the delay time and the starting time of jobs to improve the solution obtained by using the genetic algorithm. A comparison of the numerical experiments with CPLEX and the literature demonstrates the validity of the algorithm.