基于LIB的有色箱覆盖问题

摘要：

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方.该问题是一个新的组合优化问题,来源于多处理器任务调度.给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论.

关键词：箱覆盖问题、调度问题、组合优化、近似算法、最坏情况渐进性能比

所属期刊栏目：29

分类号：TP301(计算技术、计算机技术)

资助基金：湖南省教育厅科研基金项目06C126

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

页数：共3页

页码：2269-2271