基于物品移动的局内装箱算法的改进
  修订日期:2007-05-20  点此下载全文
引用本文:杨鼎强,王晨.基于物品移动的局内装箱算法的改进[J].计算技术与自动化,2008,(2):44-48
摘要点击次数: 1788
全文下载次数: 380
杨鼎强  王晨
[1]长沙理工大学计算机通讯工程学院,湖南长沙410076 [2]湖南现代物流职业技术学院信息系,湖南长沙410001
基金项目:国家自然科学基金 , 湖南省社会科学基金
中文摘要:局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.
中文关键词:装箱问题  局内算法  近似算法  复杂性
 
Improved Bound of Online Bin-packing Algorithm Based on Move Model
YANG Ding-qiang  WANG Chen
查看全文   查看/发表评论   下载pdf阅读器