Bin Packing and Machine Scheduling
2. Insights into solving hard problems
L = (1/2, 1/2N, 1/2, 1/2N, ...., 1/2)
where N is a positive integer which is 2 or bigger. NF applied to this list will produce a packing which has 2N bins, each bin packed with an item of weight 1/2 at the bottom and an item of weight 1/2N on top. However, the optimal packing for this list uses N + 1 bins: N bins, each with two weights of size 1/2, and one additional bin to contain the N items of size 1/2N. Below are some diagrams to help visualize the packing which is optimal versus what happens when NF is used. (The optimal packing has N copies of the one bin pictured on the far left and one copy of the next bin. The NF packing has 2N copies of the bin on the far right. The blue denotes unused space.)
Over a period of about 30 years, researchers have examined a wide variety of variants of bin packing algorithms and obtained increasingly better worst case analyses of the different algorithms. For example, First Fit does significantly better than NF but not spectacularly so:
where , the ceiling function, denotes the smallest integer greater than or equal to y. One can construct a family of lists that show that this bound is the best (asymptotically). Furthermore, examining examples for which particular algorithms do not perform well often provides clues for finding improved algorithms.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance