【摘要】 作为经典装箱问题的扩展,有色装箱问题在多处理器实时调度的过程中有很强的应用背景。论文提出了有色装箱问题的新算法-SCPF算法,按颜色分类,将相同颜色的物品分成一类。放置时按照相同颜色的物品首先放置的原则,将物品进行装箱。实验证明,该算法与文献犤3犦中的KC-A算法相比具有更好的装箱效果,使用的箱子数更少。并从理论上论证了该算法的性能比KC-A算法更好。更多还原

【Abstract】 As the extension of classical bin packing problems (BPP),coloring BPP has many important applications in multi-processor real-time scheduling.A new approximation algorithm,named SCPF,is proposed in this paper.After classi-fying the objects according to the same colors,SCPF packs the objects in the same class with the same color firstly.Ex-periment shows better results and fewer boxes for SCPF than that for KC-A algorithm presented in referenc . A demonstration is also made to show the better performance ratio of SCPF in theory.更多还原