带振荡策略的启发式算法求解一类新型分配问题

提出了一种新型的分配问题，该问题来源于钢铁企业中的板坯优化管理.与一般分配问题相比，该问题在将物品分配给背包时，除了需满足背包的容量限制外，还需满足流向限制.此问题可归结为 一般分配问题，因此为NP难问题.针对该问题，提出了带有振荡策略和长期表的启发式算法求解.振荡策略使局部搜索算法在可行区域和不可行区域间振荡，以获得更好的近优解；其次，在算法中引入了禁忌搜索的长期表，根据频率鼓励物品的多样性移动，提高算法的分散搜索能力.为验证算法有效性， 对随机产生的23种规模的数据进行了实验.实验结果表明：对于小规模数据，算法结果与最优解的最大偏差为0.55{\%}；在大规模情况下，算法能在快速的时间内获得问题的近优解.

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 improvethe 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.