A novel discrete state transition algorithm for staff assignment problem
DONG Tian-xue
YANG Chun-hua
ZHOU Xiao-jun
GUI Wei-hua
Abstract：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 algo-rithm 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.
Keywords：assignment problemdiscrete state transition algorithmsecond transitionstagnation backtrackinginteger programming
Publication Date：2016-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：11( 1378-1388 )