| 带约束的一维装箱问题近似算法的研究 |
| |
| 引用本文： | 董一鸿,赵杰煜.带约束的一维装箱问题近似算法的研究[J].计算机工程与应用,2003,39(18):41-44. |
| |
| 作者姓名： | 董一鸿 赵杰煜 |
| |
| 作者单位： | 宁波大学信息科学与工程学院计算机系,宁波,315211 |
| |
| 基金项目： | 国家自然科学基金(编号:60273094)资助 |
| |
| 摘 要： | 作为经典装箱问题的扩展,有色装箱问题在多处理器实时调度的过程中有很强的应用背景。论文提出了有色装箱问题的新算法-SCPF算法,按颜色分类,将相同颜色的物品分成一类。放置时按照相同颜色的物品首先放置的原则,将物品进行装箱。实验证明,该算法与文献犤3犦中的KC-A算法相比具有更好的装箱效果,使用的箱子数更少。并从理论上论证了该算法的性能比KC-A算法更好。
|
| 关 键 词： | 装箱问题 组合优化 近似算法 多处理器调度 |
| 文章编号： | 1002-8331-(2003)18-0041-04 |
| 修稿时间： | 2003年3月1日 |
Approximation Algorithms for the Constrained Bin Packing Problem |
| |
| Dong Yihong Zhao Jieyu.Approximation Algorithms for the Constrained Bin Packing Problem[J].Computer Engineering and Applications,2003,39(18):41-44. |
| |
| Authors: | Dong Yihong Zhao Jieyu |
| |
| 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. |
| |
| Keywords: | bin packing problem combinational optimization approximation algorithm multi-process scheduling |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
