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

摘要：

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

关键词：分配问题、振荡策略、长期表

所属期刊栏目：29

分类号：N94(系统科学)

资助基金：国家自然科学青年基金60804053

在线出版日期：2009-03-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：111-117