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

On constrained coloring bin packing problem with longest item at bottom

作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题(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.