一类带多重核元集在线装箱问题

A Class of On-line Bin Packing Problems with Multiple Kernels

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.

We consider a new class of on-line variable-sized bin packing problems as follows:suppose the size of bins are varied.Given a list of items and a kernel relation graph G on items.One needs to put them into bins which arrive on time one by one or batch by batch,and the induce graph of items packed into each bin must be empty graph.The objective is to minimize the total size of bins used.We propose some approximation algorithms based on graph coloring,graph clique partition and knapsack problem.We give the performance bound of proposed algorithms.