7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

Five boxes weigh 5 kg, 2 kg, 4 kg, 3 kg and 8 kg. They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg.

1. Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins. [2]
2. Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins. [2]
3. Why might the first-fit decreasing method not be practical? [1]
4. Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins. [1]

The memory requirements, in KB, for eight computer files are given below. 43 \quad 172 \quad 536 \quad 17 \quad 314 \quad 462 \quad 220 \quad 231 The files are to be grouped into folders. No folder is to contain more than 1000 KB, so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders. [3]
2. Use the first-fit decreasing method to group the files into folders. [3]

First-fit decreasing is a quadratic order algorithm.

1. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers? [2]

A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$150 \quad 104 \quad 200 \quad 60 \quad 184 \quad 84 \quad 120$$

1. Perform a quick sort to put the seven lengths in descending order. [4 marks]

The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.

1. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed. [4 marks]
2. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods. [1 mark]

A steel manufacturer has 3 factories \(F_1\), \(F_2\) and \(F_3\) which can produce 35, 25 and 15 kilotomnes of steel per year, respectively. Three businesses \(B_1\), \(B_2\) and \(B_3\) have annual requirements of 20, 25 and 30 kilotomnes respectively. The table below shows the cost \(C_{ij}\) in appropriate units, of transporting one kilotome of steel from factory \(F_i\) to business \(B_j\).

		Business
	\(B_1\)	\(B_2\)	\(B_3\)
\(F_1\)	10	4	11
Factory \(F_2\)	12	5	8
\(F_3\)	9	6	7

The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule. [2]
2. Calculate all of the improvement indices \(I_{ij}\) and hence show that this pattern is not optimal. [5]
3. Use the stepping-stone method to obtain an improved solution. [3]
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost. [4]

1. Describe a practical problem that could be solved using the transportation algorithm. [2]

A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from \(A\), \(B\) and \(C\) and the demand is at \(d\) and \(e\).

1. Explain why it is necessary to add a third demand \(f\). [1]
2. Use the north-west corner rule to obtain a possible pattern of distribution and find its cost.

   	\(d\)	\(e\)	\(f\)	Supply
   \(A\)	5	3		45
   \(B\)	4	6		35
   \(C\)	2	4		40
   Demand	50	60

   [5]
3. Calculate shadow costs and improvement indices for this pattern. [5]
4. Use the stepping-stone method once to obtain an improved solution and its cost. [5]

(Total 16 marks)

The masses, in kg, of ten bags are given below. 8 \quad 10 \quad 10 \quad 12 \quad 12 \quad 12 \quad 13 \quad 15 \quad 18 \quad 18

1. Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. [3]

Only two crates are available, so only some of the bags will be packed. Each bag is given a value.

Bag	A	B	C	D	E	F	G	H	I	J
Mass (kg)	8	10	10	12	12	12	13	15	18	18
Value	6	3	3	2	4	5	4	6	4	4

1. Find a packing into two crates so that the total value of the bags in the crates is at least 32. [3]

17 & 9 & 15 & 8 & 20 & 13 & 28 & 4 & 12 & 5 \end{array}$$ The numbers in the list shown above are the weights, in kilograms, of ten boxes. The boxes are to be transported in containers that will each hold a maximum weight of 40 kilograms.

1. Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.
2. Use the first-fit bin packing algorithm to allocate the boxes to the containers.
3. Using the list provided, carry out a quick sort to produce a list of the weights in ascending order. You must make your pivots clear.
4. Use the binary search algorithm to try to locate the weight of 9 in the sorted list. Clearly indicate how you choose your pivots and which part of the list is being rejected at each stage.