A class of on-line bin packing problems with multiple kernels

A class of on-line bin packing problems with multiple kernels

0.00 Avg rating0 Votes
Article ID: iaor20062300
Country: China
Volume: 18
Issue: 3
Start Page Number: 411
End Page Number: 416
Publication Date: Jul 2005
Journal: Mathematica Applicata
Authors: ,
Keywords: bin packing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.