受位置约束的有色装箱问题  

On constrained coloring bin packing problem with longest item at bottom

作　　者：杨鼎强[1] 王晨 

机构地区：[1]长沙理工大学计算机通信工程学院,湖南长沙410076 [2]中国湖南国际经济合作公司,湖南长沙410001

出　　处：《计算机工程与设计》2006年第20期3864-3866,共3页Computer Engineering and Design

摘　　要：作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题(longest item at the bottom coloring bin packingproblem,LIBCBPP),即在有色物品的装箱过程中,要求重(长)的物品置于轻(短)的物品下方。该问题在任务调度和日常生活中的运输等问题中有着广泛的应用背景。给出了一个求解该问题的近似KC-LIBFF算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果。As the extension of coloring bin packing problem （BPP）, a constrained coloring bin packing problem with longest item at the bottom （LIBCBPP） is proposed, in which an additional longest item at the bottom is needed if different color items are put into a same bin. The problem has many applications such as multiprocessor scheduling and real-world transportation. An approximation algorithm KC-LIBFF is presented to solve the LIBCBPP problem. It is proved that the KC-LIBFF algorithm has an asymptotic worst-case performance ratio of 2, finally the experimental results are given.

关 键 词：装箱问题 调度问题 组合优化 近似算法 最坏情况渐进性能比 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]