基于LIB的有色箱覆盖问题

Coloring bin covering problem based on longest item at the bottom

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方。该问题是一个新的组合优化问题,来源于多处理器任务调度。给出一个求解该问题的局内近似算法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.