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

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

ONLINE APPROXIMATION ALGORITHMS FOR COLORING BIN PACKING PROBLEM

As one of the constrained bin packing problems (BPP), coloring BPP has many important applications such as multi processor real time scheduling, etc . An approximation algorithm, called KC A , to solve the coloring BPP is proposed in this paper. It classifies the inputs first and then packs the objects in the same class with classical bin packing algorithm A . Also given are a lower bound of the worst case asymptotic performance ratio of KC A and analysis of the asymptotic worst case, average case performance ratio of the KC A algorithm when A is NF, FF, BF or WF . Finally the experimental results are given. KC FF shows a better result in the experiment.