有色装箱问题的在线近似算法

摘要：

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.提出了求解有色装箱问题的KC-A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A;给出了KC-A算法最坏情况渐近性能比的下界;分析了当选用的算法A是著名装箱算法NF,FF,BF,WF时KC-A算法的最坏情况渐近性能比和平均性能比;给出了实验结果,并指出KC-FF表现出相对更好的实验效果.

关键词：装箱问题、调度问题、组合优化、近似算法、渐近性能比

所属期刊栏目：39

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

资助基金：国家重点基础研究发展计划973计划G1998030403

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

页数：共7页

页码：335-341