A new variable-sized bin packing problem

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TidsskriftJournal of Scheduling
Vol/bind15
Udgave nummer3
Sider (fra-til)273-287
ISSN1094-6136
DOI
StatusUdgivet - 2012

Fingeraftryk

Bins
Genes
DNA sequences
Bin packing
Scenarios
Data base

Emneord

  • Online bin packing
  • variable-sized bins
  • bins arriving on-line
  • parallilization of BLAST jobs

Citer dette

@article{28273ebdda6e42a0b854531b023ecc54,
title = "A new variable-sized bin packing problem",
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.",
keywords = "Online bin packing, variable-sized bins, bins arriving on-line, parallilization of BLAST jobs",
author = "Joan Boyar and Favrholdt, {Lene Monrad}",
year = "2012",
doi = "10.1007/s10951- 010-0199-4",
language = "English",
volume = "15",
pages = "273--287",
journal = "Journal of Scheduling",
issn = "1094-6136",
publisher = "Springer",
number = "3",

}

A new variable-sized bin packing problem. / Boyar, Joan; Favrholdt, Lene Monrad.

I: Journal of Scheduling, Bind 15, Nr. 3, 2012, s. 273-287.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - A new variable-sized bin packing problem

AU - Boyar, Joan

AU - Favrholdt, Lene Monrad

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Online bin packing

KW - variable-sized bins

KW - bins arriving on-line

KW - parallilization of BLAST jobs

U2 - 10.1007/s10951- 010-0199-4

DO - 10.1007/s10951- 010-0199-4

M3 - Journal article

VL - 15

SP - 273

EP - 287

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 3

ER -