Aim
- To assess student ability to develop new algorithms following the principles of a chosen Algorithm Design Technique.
- To strengthen student understanding of the Greedy technique for designing algorithms.
- To provide experience of evaluating and comparing different algorithms.
General
Consider the following variation of the Bin Packing Problem, called the Truck Loading Problem (TLP).
We have an unlimited supply of two dimensional trucks, each truck having a width of W and a height of H. We also have n two dimensional boxes, with widths w1,w2,…,wn and heights h1,h2,…,hn. The problem is to load these boxes onto possibly smallest number of trucks under the following rules:
- A. A box is placed either at the bottom of a truck (starting a new pile), or on top of another box of equal or greater width.
- B. At most one box is placed directly on top of any box.
- C. The total height of any pile of boxes does not exceed H.
- D. The number of boxes placed in a truck cannot exceed L (where L is given).
Moreover, it is not allowed to rotate boxes, the sides of the boxes must be parallel to the sides of the trucks, and once a box has been placed inside a truck it cannot be moved.
Tasks (to be implemented in the Java programming language)
(1) Design and document using pseudo code the following two Greedy algorithms for solving TLP:
- NFTLP: based on next fit on-line strategy for solving Bin Packing Problem.
- FFTLP: based on first fit on-line strategy for solving Bin Packing Problem.
This strategy attempts to select the first bin which currently has sufficient space to pack an item.
(2) Design and implement data structures representing all the boxes and trucks, and provide output functions for displaying the contents of your data structures.
(3) Devise and implement methods for generating suitable sequences of integers which can then be used for measuring performance of the two algorithms. The test data should represent sequences of boxes (all test data for performance analysis must be generated within your program).
(4) Implement the two algorithms (NFTLP and FFTLP).
(5) Implement two ways of measuring the performance of the two algorithms, one based on timing their runs and the other on counting the number of trucks used for loading the boxes. Carry out measurements and comment on the results you obtained. For example, you might conclude that NFTLP is on average 25% faster than FFTLP, but it needs 20% more trucks.
Marking Scheme
The completed request must be submitted to NESS in a single .zip file.
Your submission should include the following:
- A short report, giving a description of the implementation, testing and measurements made. This does not need to be a Maintenance Manual, but should explain the overall organisation of the program, the pseudo code for the proposed algorithms, and the description of data structures used.
- The tabulated results with graphical summaries of the overall comparisons.
- Comments on the results that you have obtained.
- Source code.