COS 226 Programming Assignment: Bin Packing

COS 226 Programming Assignment

Bin packing

princetontelecomm.com has just hired you as a consultant to help them reduce costs in their customer service department. They digitally record customer service phone calls and store all the sound files on portable disks at the end of each week. Since your marginal cost is proportional to the total number of disks used, your task is to assign the sound files to disks using as few disks as possible. Since the problem is NP-complete, it seems hopeless to find an efficient algorithm for finding the optimal packing. Instead, your goal is to design heuristics that run fast and produce high quality solutions.

We formulate the bin packing problem as follows: given a set of N file sizes between 0 and 1,000,000 KB (1 GB), find a way to assign them to a minimal number of disks, each of capacity 1 GB.

The worst-fit heuristic is a simple rule that considers the file sizes in the order they are presented: if the sound file won't fit on any disk, create a new disk; otherwise place the file on a disk that has the most remaining space. For example, this algorithm would put the sizes 700,000, 800,000, 200,000, 175,000, 125,000 onto three disks: {700,000, 200,000}, {800,000, 175,000}, {125,000}. Note that this yields a suboptimal solution because the five files could fit on two disks.
The best-fit heuristic is identical, except that the file is placed on a disk that has the least space among all disks with enough room to store the file. This algorithm would put the same sequence of weights onto two disks: {800,000, 200,000}, {700,000, 175,000, 125,000}. Note that this yields an optimal solution for this small example, but it typically produces a suboptimal solution.

Your main task is to implement the worst-fit and best-fit heuristics and compare their performance (quality of solution produced and running time).

Perspective. The bin packing problem is a fundamental problem for minimizing the consumption of a scarce resource, usually space. Applications include: packing the data for Internet phone calls into ATM packets, optimizing file storage on removable media, assigning commercials to station breaks, allocating blocks of computer memory, and minimizing the number of identical processors needed to process a set of tasks by a given deadline. In the latter example, the scarce resource is time instead of space. Cloth, paper, and sheet metal manufacturers use a two-dimensional version of the problem to optimally cut pieces of material (according to customer demand) from standard sized rectangular sheets. Shipping companies use a three-dimensional version to optimally pack containers or trucks.

Disk data type. First, implement a data type Disk.java that represents a 1GB disk, and contains a list of all of the files it is storing. This data type should implement the Comparable<Disk> interface so that you can use it with a priority queue or sorted symbol table.

Data structures. You will need to choose efficient data structures in order to efficiently implement the two heuristics.

For the worst-fit heuristic, you will certainly need insert and delete the maximum operations. The priority queue MaxPQ.java is a judicious choice.
For the best-fit heuristic, the key operation is ceiling: find the smallest key greater than or equal to a given key. You will want to use some kind of binary search tree. But be careful since our symbol tables implementations do not allow duplicate keys.

Input and output. Your client program will read in the set of file sizes (guaranteed to be between zero and a million) from standard input. Your program should output the number of disks used by the heuristic and the sum of all file sizes divided by 1 million (a lower bound on the number of disks required). If the number of files is less than 100, you should also print out the disks in increasing order of remaining space. For each disk, print out its remaining space and its contents (in the order the file sizes were inserted). Optionally, you may also print out a unique id associated with each disk (assigned in the order the disks were created) to aid in debugging.

% java WorstFit < input20.txt
Sum of all files = 6.580996 GB
Disks used       = 8
      1   82266:  311011 286309 320414
      2  109806:  396295 230973 262926
      3  116563:  347560 204065 331812
      6  142051:  340190 263485 254274
      4  190811:  324387 484802
      7  224009:  383972 392019
      0  227744:  420713 351543
      5  325754:  347661 326585

java BestFit < input20.txt 
Sum of all files = 6.580996 GB
Disks used       = 8
      0   23679:  420713 351543 204065
      8   57143:  347560 331812 263485
     13   71480:  347661 326585 254274
      2   82266:  311011 286309 320414
      5  109806:  396295 230973 262926
     11  190811:  324387 484802
     15  275838:  340190 383972
     19  607981:  392019

Worst-fit and best-fit decreasing. Experienced travelers know that if small items are packed last, they can fit snugly in the odd gaps in nearly filled luggage. This motivates a smarter strategy: process the items from biggest to smallest. The worst-fit decreasing heuristic is to do worst-fit, but first preprocess the file sizes so that they are in descending order; the best-fit decreasing heuristic is to do best-fit, but first preprocess the file sizes so that they are in descending order; A modular way to implement this heuristic is to write a separate program IntegerReverseSorter.java that reads in a sequence of integers and prints them out in descending order. Then you can pipe the results through your worst-fit and best-fit heuristics.

% java IntegerReverseSorter < input20.txt | java WorstFit
Sum of all files = 6.580996 GB
Disks used       = 7
      2    1000:  383972 351543 263485
      4    1413:  340190 331812 326585
      3   18470:  347661 347560 286309
      5   44188:  324387 320414 311011
      6   47762:  262926 254274 230973 204065
      0   94485:  484802 420713
      1  211686:  396295 392019

% java IntegerReverseSorter < input20.txt | java BestFit
Sum of all files = 6.580996 GB
Disks used       = 7
      4    1000:  383972 351543 263485
      8    1413:  340190 331812 326585
      2    7621:  396295 392019 204065
      6   18470:  347661 347560 286309
     11   44188:  324387 320414 311011
      0   94485:  484802 420713
     16  251827:  262926 254274 230973

Analysis. Run your heuristics on a variety of inputs, with N = 100, 1,000, 10,000, 100,000, and 1,000,000. Do a few trials for each value of N using random weights between zero and one million. In your writeup, comment on the relative effectiveness (number of disks used) of the four heuristics (worst-fit, worst-fit decreasing, best-fit, and best-fit decreasing).

Submission. Your main programs should be named WorstFit.java, BestFit.java and IntegerReverseSorter.java. Submit all of the other files needed by your program (e.g., Disk.java). You do not need to submit StdIn.java, StdOut.java, MinPQ.java, or MaxPQ.java. Also include a readme.txt file as usual.

Extra Credit. Design and implement a heuristic that consistently beats worst-fit decreasing and best-fit decreasing. Your algorithm should work for large N so it must take time proportional to N log N. One idea is first-fit decreasing where you insert the next file in the first disk that has enough room to store it. Use a heap-like structure called a tournament tree.