| 引用本文: | 董天雪,阳春华,周晓君,桂卫华.一种求解企业员工指派问题的离散状态转移算法[J].控制理论与应用,2016,33(10):1378~1388.[点击复制] |
| Dong Tianxue,YANG Chun-hua,ZHOU Xiao-jun,GUI Wei-hua.A novel discrete state transition algorithm for staff assignment problem[J].Control Theory and Technology,2016,33(10):1378~1388.[点击复制] |
|
| 一种求解企业员工指派问题的离散状态转移算法 |
| A novel discrete state transition algorithm for staff assignment problem |
| 摘要点击 3545 全文点击 1510 投稿时间：2015-12-10 修订日期：2016-09-30 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2016.50982 |
| 2016,33(10):1378-1388 |
| 中文关键词 指派问题 离散状态转移算法 二次状态转移 停滞回溯 整数规划 |
| 英文关键词 assignment problem discrete state transition algorithm second transition stagnation backtracking integer programming |
| 基金项目 国家自然科学基金项目(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. |
|
|
|
|
|