Best Fit Bin Packing

Many types of computational problems can be mapped to ‘bin packing’. Scheduling of jobs on a set of available machines is one such problem which is common in job shop type environments.

Here is some F# code that implements the ‘best fit’ heuristic algorithm for bin packing:

http://fssnip.net/hG

Also provided is an implementation of binary tree with duplicates for tracking remaining bin capacities:

Lets say you have 100 customer orders for cutting plywood in various configurations. Each job requires Xj centimeters of cutting (j=1..100). You also have 10 electric saws that can cut at the rates of Ym centimeters / hour (m=1..10). Given 8 hours in a working day your problem is to best schedule the jobs on the available machines to maximize the machine utilization.

This type of problem can be modeled as a 1-dimensional bin packing problem. Scheduling of jobs to machines is akin to putting items of different sizes into a set of bins of different capacities.

Bin packing is a NP-hard problem but there are reasonable heuristic algorithms available as solutions. One such algorithm is best fit and its variant decreasing order best fit. The decreasing-order variant offers better performance and can be easily achieved by sorting the items in decreasing order of size prior to invoking the best fit algorithm.

Implementation of best fit requires keeping tracking of remaining bin capacities as each item is added. The referenced F# implementation uses a binary tree with duplicates for O(log(n)) lookup of bins based on the remaining capacity.

 

 

Advertisements

One thought on “Best Fit Bin Packing

  1. Pingback: Visualizing a Schedule usign F# and the .Net Visualization Library | Faisal's space

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s