This module implements a number of common bin packing heurstics: FirstFit
,
LastFit
, BestFit
, WorstFit
, and AlmostWorstFit
. In addtion, the
not-so-common, but analytically superior (in terms of worst-case behavior),
ModifiedFirstFit
heuristic is also supported. Items can be packed in order of
both Decreasing
and Increasing
size (and, of course, in unmodified order;
see AsGiven
).
The module supports both the standard (textbook) minimization problem
("How many bins do I need to pack all items?"; see minimizeBins
and
countBins
) and the more practical fitting problem
("I've got n bins; which items can I take?"; see binpack
).
The well-known heuristics are described online in many places and are not
further discussed here. For example, see
http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm for an overview. A
description of the ModifiedFirstFit
algorithm is harder to come by online,
hence a brief description and references are provided below.
Note that most published analysis assumes items to be sorted in some specific
(mostly Decreasing
) order. This module does not enforce such assumptions,
rather, any ordering can be combined with any placement heuristic.
If unsure what to pick, then try FirstFit
Decreasing
as a default. Use
BestFit
(in combination with binpack
) if you want your bins filled
evenly.
A short overview of the ModifiedFirstFit
heuristic follows. This overview is
based on the description given in (Yue and Zhang, 1995).
Let lst
denote the list of items to be bin-packed, let x
denote the size of
the smallest element in lst
, and let cap
denote the capacity of one
bin. lst
is split into the four sub-lists, lA
, lB
, lC
, lD
.
lA
- All items strictly larger than
cap/2
. lB
- All items of size at most
cap/2
and strictly larger thancap/3
. lC
- All items of size at most
cap/3
and stricly larger than(cap - x)/5
. lD
- The rest, i.e., all items of size at most
(cap - x)/5
.
Items are placed as follows:
- Create a list of
length lA
bins. Place each item inlA
into its own bin (while maintaining relative item order with respect tolst
). Note: relevant published analysis assumes thatlst
is sorted in order ofdecreasing
size. - Take the list of bins created in Step 1 and reverse it.
- Sequentially consider each bin
b
. If the two smallest items inlC
do NOT fit together intob
of if there a less than two items remaining inlC
, then pack nothing intob
and move on to the next bin (if any). If they do fit together, then find the largest itemx1
inlC
that would fit together with the smallest item inlC
intob
. Removex1
fromlC
. Then find the largest itemx2
,x2 \= x1
, inlC
that will now fit intob
together withx1
. Removex1
fromlC
. Place bothx1
andx2
intob
and move on to the next item. - Reverse the list of bins again.
- Use the
FirstFit
heuristic to place all remaining items, i.e.,lB
,lD
, and any remaining items oflC
.
References:
- D.S. Johnson and M.R. Garey. A 71/60 Theorem for Bin-Packing. Journal of Complexity, 1:65-106, 1985.
- M. Yue and L. Zhang. A Simple Proof of the Inequality MFFD(L) <= 71/60 OPT(L) + 1, L for the MFFD Bin-Packing Algorithm. Acta Mathematicae Applicatae Sinica, 11(3):318-330, 1995.
- data PlacementPolicy
- = FirstFit
- | ModifiedFirstFit
- | LastFit
- | BestFit
- | WorstFit
- | AlmostWorstFit
- data OrderPolicy
- = AsGiven
- | Decreasing
- | Increasing
- type Measure a b = b -> a
- type Bin = []
- allOrders :: [OrderPolicy]
- allPlacements :: [PlacementPolicy]
- allHeuristics :: [(PlacementPolicy, OrderPolicy)]
- minimizeBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> ([a], [Bin b])
- countBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> Int
- binpack :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> [a] -> [b] -> ([a], [Bin b], [b])
Documentation
data PlacementPolicy Source
What placement heuristic should be used?
FirstFit | Traverse bin list from |
ModifiedFirstFit | See above. |
LastFit | Traverse bin list from |
BestFit | Place item in the bin with the most capacity. |
WorstFit | Place item in the bin with the least (but sufficient) capacity. |
AlmostWorstFit | Choose the 2nd to worst-fitting bin. |
data OrderPolicy Source
How to pre-process the input.
AsGiven | Don't modify item order. |
Decreasing | Sort from largest to smallest. |
Increasing | Sort from smallest to largest. |
allOrders :: [OrderPolicy]Source
The list of all possible OrderPolicy
choices. Useful for benchmarking.
allPlacements :: [PlacementPolicy]Source
The list of all possible PlacmentPolicy
choices. Useful for benchmarking.
allHeuristics :: [(PlacementPolicy, OrderPolicy)]Source
All supported ordering and placment choices. Useful for benchmarking.
:: (Num a, Ord a) | |
=> PlacementPolicy | How to order the items before placement. |
-> OrderPolicy | The bin packing heuristic to use. |
-> Measure a b | How to size the items. |
-> a | The size of one bin. |
-> [b] | The items. |
-> ([a], [Bin b]) | The result: a list of the remaining capacities and a list of the bins. |
Bin packing without a limit on the number of bins (minimization problem). Assumption: The maximum item size is at most the size of one bin (this is not checked).
Examples:
- Pack the words of the senctene "Bin packing heuristics are a lot of fun!"
into bins of size 11, assuming the size of a word is its length.
The
Increasing
ordering yields a sub-optimal result that leaves a lot of empty space in the bins.
minimizeBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!") ~~> ([1,4,4,2],[["heuristics"],["packing"],["fun!","lot"],["are","Bin","of","a"]])
- Similarly, for
Int
. Note that we useid
as theMeasure
for the size of anInt
. In this case, all bins are full.
minimizeBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4] ~~> ([0,0,0],[[2,3,3,3],[4,7],[1,10]])
countBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> IntSource
Wrapper around minimizeBins
; useful if only the number of required
bins is of interest. See minimizeBins
for a description of the arguments.
Examples:
- How many bins of size 11 characters each do we need to pack the words of the sentence "Bin packing heuristics are a lot of fun!"?
countBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!") ~~> 4
countBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4] ~~> 3
:: (Num a, Ord a) | |
=> PlacementPolicy | The bin packing heuristic to use. |
-> OrderPolicy | How to order the items before placement. |
-> Measure a b | How to size the items. |
-> [a] | Intitial per-bin capacities. |
-> [b] | The items. |
-> ([a], [Bin b], [b]) | The result; a list of residue capacities, the bins, and a list of items that could not be placed. |
Bin pack with a given limit on the number (and sizes) of bins. Instead of creating new bins, this version will return a list of items that could not be packed (if any).
Example: We have two bins, one of size 10 and one of size 12. Which words can we fit in there?
binpack WorstFit Decreasing length [10, 12] (words "Bin packing heuristics are a lot of fun!") ~~> ([0,0],[["heuristics"],["a","fun!","packing"]],["of","lot","are","Bin"])