Heuristic algorithm with oscillation strategy for a new class of assignment problem

A new class of assignment problem is proposed in this paper, which roots in the optimization management of slabs in steel industry. Comparing with the generalized assignment problem, flow constraints should be considered in this problem besides the capacity constraints when assign items to knapsacks. This problem could be reduced to the generalized assignment problem, and so is NP-hard. For this problem, a heuristic with oscillation strategy and long-term memory list is proposed to solve it. The oscillation strategy makes it possible that the local search oscillates between the feasible and unfeasible solution spaces in order to find better feasible solutions. Long-term memory list is embedded to encourage the diverse moves of items, which helps to improve the scattered search ability of the algorithm. In order to testify the efficiency of the heuristic, 23 instances have been randomly generated for the computational experiments. The results show that: for small size problems, the maximum deviation of the heuristic from the optimal solution is 0.55%; for larger size problems, the heuristic could find good solutions in very short time.