A new variable‐sized bin packing problem

A new variable‐sized bin packing problem

0.00 Avg rating0 Votes
Article ID: iaor20123921
Volume: 15
Issue: 3
Start Page Number: 273
End Page Number: 287
Publication Date: Jun 2012
Journal: Journal of Scheduling
Authors: ,
Keywords: combinatorial optimization, scheduling
Abstract:

The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. This results in a new variant of bin packing, where a rectangle is divided into smaller rectangles that are to be packed in variable‐sized bins which arrive on‐line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle. Simple algorithms exist that work well on small instances of the problem and in the special case where all processors (bins) have the same capacity. We propose an algorithm Slices that works well for more realistic instances in a scenario where the processors vary significantly and arrive on‐line.

Reviews

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