Ruby scripts that attempt to provide implementations of various bin packing problems algorithms.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
LICENSE
README.rdoc
firstfit
firstfit_tests
firstfititerativeresort
firstfititerativeresort_tests

README.rdoc

Solutions for Bin Packing Variable Sized Segregate Type Items in Variable Sized Bins

These Ruby scripts test bin packing algorithms that take input of a variable number of items of variable size that must be segregated by type into a variable number of variable size bins.

So, given some items and bins, it determines how to put those items in the bins while attempting to:

  • put items of the same type together in a bin, with no items of other types stored in the same bin

  • reduce empty space in used bins

  • use fewer bins

  • use bins of smaller size

(in that order of preference)

These scripts do not guarantee best-fit.

How to Use

Install Git and Ruby.

Clone this project.

cd ~
git clone http://github.com/garysweaver/bestfit.git

Examples

Segregated First-fit Decreasing

The segregated first-fit decreasing implementation is fairly trivial. It sorts items first by type, then size descending, then puts them into bins of ascending size, if the type matches, and if there is space.

$ ./firstfit --items notebook:school:1,war_and_peace:school:3,cookbook:home:2,some_shoes:shoes:1 --bins bag:3,box:1,big_box:4,other_bag:2
bag:3:0 : war_and_peace:school:3
big_box:4:3 : some_shoes:shoes:1
box:1:0 : notebook:school:1
other_bag:2:0 : cookbook:home:2

The first-fit tests allow you to test out first-fit to some extent:

$ ./firstfit_tests --num-items 1000 --item-max-size 16 --num-types 100 --num-bins 700 --bin-max-size 32

...

Wasted space in used bins: 1683 / 10278 = % 16.3747810858144

You can also specify specific sizes of items and bins:

./firstfit_tests --num-items 100 --item-sizes 1,3,7,13,18,21 --num-types 35 --num-bins 800 --bin-sizes 22,26,38,40,70

...

Wasted space in used bins: 367 / 1408 = % 26.0653409090909

Segregated First-fit Decreasing with Iterative Bin Resort

The segregated first-fit decreasing with iterative bin resort implementation is just like the segregated first-fit decreasing, but it resorts the available bins by available space after each item is put into a bin. This takes significantly longer and doesn't seem to offer much advantage for reasons that may be obvious.

$ ./firstfititerativeresort --items notebook:school:1,war_and_peace:school:3,cookbook:home:2,some_shoes:shoes:1 --bins bag:3,box:1,big_box:4,other_bag:2
bag:3:0 : war_and_peace:school:3
big_box:4:3 : some_shoes:shoes:1
box:1:0 : notebook:school:1
other_bag:2:0 : cookbook:home:2

The first-fit iterative bin resort tests allow you to test out first-fit iterative resort to some extent:

$ ./firstfititerativeresort_tests --num-items 1000 --item-max-size 16 --num-types 100 --num-bins 700 --bin-max-size 32

...

Wasted space in used bins: 1642 / 10013 = % 16.3986817137721

You can also specify specific sizes of items and bins:

./firstfititerativeresort_tests --num-items 100 --item-sizes 1,3,7,13,18,21 --num-types 35 --num-bins 800 --bin-sizes 22,26,38,40,70

...

Wasted space in used bins: 376 / 1430 = % 26.2937062937063

See Also

For more information, see the Wikipedia entry, Bin Packing Problem, as well as the fine paper, Algorithms for the variable sized bin packing problem, by Jangha Kang and Sungsoo Park from the European Journal of Operational Research, Volume 147, Issue 2, 1 June 2003, Pages 365–372.

License

Copyright © 2012 Gary S. Weaver, released under the MIT license.