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 than`cap/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 in`lA`

into its own bin (while maintaining relative item order with respect to`lst`

). Note: relevant published analysis assumes that`lst`

is sorted in order of`decreasing`

size. - Take the list of bins created in Step 1 and reverse it.
- Sequentially consider each bin
`b`

. If the two smallest items in`lC`

do NOT fit together into`b`

of if there a less than two items remaining in`lC`

, then pack nothing into`b`

and move on to the next bin (if any). If they do fit together, then find the largest item`x1`

in`lC`

that would fit together with the smallest item in`lC`

into`b`

. Remove`x1`

from`lC`

. Then find the largest item`x2`

,`x2 \= x1`

, in`lC`

that will now fit into`b`

*together*with`x1`

. Remove`x1`

from`lC`

. Place both`x1`

and`x2`

into`b`

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 of`lC`

.

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 use`id`

as the`Measure`

for the size of an`Int`

. 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"])