基于LIB的有色箱覆盖问题  

Coloring bin covering problem based on longest item at the bottom

作　　者：杨鼎强[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,湖南长沙410076

出　　处：《计算机工程与设计》2008年第9期2269-2271,共3页Computer Engineering and Design

基　　金：湖南省教育厅科研基金项目(06C126)

摘　　要：提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论。A constrained coloring bin covering problem with longest item at the bottom （LIB） is proposed, in which an additional longest item at the bottom is needed if different color items are put into a same bin. This is a new combinatorial optimization problem which has many applications in practice, such as in multiprocessor scheduling and real-world transportation. An approximation algorithm KC-LIBFF is presented to solve the coloring bin covering problem. It is proved that the KC-LIBFF algorithm has an asymptotic worstcase perfor-mance ratio of 0, and the experimental results are given. Moreover lower worst-case bounds of any online algorithms are provided.

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

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