一种求解企业员工指派问题的离散状态转移算法
A novel discrete state transition algorithm for staff assignment problem

员工指派问题是运筹学中的一类整数规划问题, 为了寻找最佳的员工指派方案, 使得完成所有任务的总成 本代价最小, 本文研究了一种新的离散状态转移算法. 在一次状态转移的基础上提出了二次状态转移的概念, 从而 扩大了候选解集的范围, 并提高候选解集的多样性. 为了克服算法在迭代后期更新缓慢的缺点, 提出了停滞回溯策 略, 即当算法陷入局部最优解时进行回溯操作, 从历史停滞解中随机选择一个更新当前最优解. 通过与模拟退火算 法进行测试比较实验, 证明了本文所提出算法的有效性, 同时该算法提高了求解员工指派问题的成功率与稳定性.
The staff assignment problem is a kind of integer programming problem in operations research. In order to find the optimal staff assignment scheme with minimal total cost, this paper proposes a novel discrete state transition algorithm and puts forward the concept of second transition on the basis of first transition, which is helpful to expand the range of candidate solutions and improve the diversity of the candidates. To overcome the shortcomings of slow convergence of the algorithm at a later stage, stagnation backtracking strategy is proposed; that is to say, when the algorithm is stagnated into local minima, the backtracking operation is performed, and the current optimal solution is randomly selected from previously stagnant solutions. Finally, the experiments are verified and compared with the simulated annealing algorithm to prove the validity of these two strategies. Simulation results have showed the effectiveness of the improved method . Meanwhile, the method can improve the success rate and stability for this problem.