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