| 有色装箱问题的一种新的近似算法 |
| |
| 引用本文： | 刘春霞,于洪霞.有色装箱问题的一种新的近似算法[J].佳木斯大学学报,2005,23(4):606-609. |
| |
| 作者姓名： | 刘春霞 于洪霞 |
| |
| 作者单位： | 大连理工大学应用数学系,辽宁大连 116024 |
| |
| 摘 要： | 作为经典装箱问题的推广,有色装箱问题在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.本文提出了有色装箱问题的一种新的近似算法--交叉装箱算法（简称JCBP）,该算法首先对物品按长度进行排列,再从两头交叉进行装箱.实验证明,该算法较其他算法有较好的装箱效果,并且很多情况下能达到最优解.
|
| 关 键 词： | 装箱问题 近似算法 多处理器调度 |
| 文章编号： | 1008-1402（2005）04-0606-04 |
| 收稿时间： | 2005-07-11 |
| 修稿时间： | 2005年7月11日 |
A New Approximation Algorithm for Coloring Bin Packing |
| |
| LIU Chun-xia,YU Hong-xia.A New Approximation Algorithm for Coloring Bin Packing[J].Journal of Jiamusi University(Natural Science Edition),2005,23(4):606-609. |
| |
| Authors: | LIU Chun-xia YU Hong-xia |
| |
| Institution: | Department of Applied Mathematics,Dalian University of Technology,Dalian 116024,China |
| |
| Abstract: | As one of the constrained bin packing problem(BPP),coloring BPP has many important applications such as multi-processor real-time scheduling,etc.A new approximation algorithm,named JCBP,to solve the coloring BPP is proposed in this paper.After arranging the objects according to the length,JCBP packs the objects from two sides.Experiment shows better results and fewer boxes for JCBP than those for other algorithms.It also can reach the optimal solutions in many cases. |
| |
| Keywords: | bin packing approximation algorithm multi - process scheduling |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
