一种求解企业员工指派问题的离散状态转移算法  

A novel discrete state transition algorithm for staff assignment problem

作　　者：董天雪 阳春华[1] 周晓君[1] 桂卫华[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《控制理论与应用》2016年第10期1378-1388,共11页Control Theory & Applications

基　　金：国家自然科学基金项目(61533021;61503416);中南大学创新驱动计划项目(2015cx007);中南大学探索项目(7131253)资助~~

摘　　要：员工指派问题是运筹学中的一类整数规划问题,为了寻找最佳的员工指派方案,使得完成所有任务的总成本代价最小,本文研究了一种新的离散状态转移算法.在一次状态转移的基础上提出了二次状态转移的概念,从而扩大了候选解集的范围,并提高候选解集的多样性.为了克服算法在迭代后期更新缓慢的缺点,提出了停滞回溯策略,即当算法陷入局部最优解时进行回溯操作,从历史停滞解中随机选择一个更新当前最优解.通过与模拟退火算法进行测试比较实验,证明了本文所提出算法的有效性,同时该算法提高了求解员工指派问题的成功率与稳定性.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. © 2016, Editorial Department of Control Theory & Applications South China University of Technology. All right reserved.

关 键 词：指派问题 离散状态转移算法 二次状态转移 停滞回溯 整数规划 

分 类 号：O221.4[理学—运筹学与控制论]