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

1 An airline allows each passenger to carry a maximum of 25 kg in luggage. The four members of the Adams family have bags of the following weights (to the nearest kg ): The bags need to be grouped into bundles of 25 kg maximum so that each member of the family can carry a bundle of bags.

1. Use the first-fit method to group the bags into bundles of 25 kg maximum. Start with the bags belonging to Mr Adams, then those of Mrs Adams, followed by Sarah and finally Tim.
2. Use the first-fit decreasing method to group the same bags into bundles of 25 kg maximum.
3. Suggest a reason why the grouping of the bags in part (i) might be easier for the family to carry.

4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to \(30000 \mathrm {~cm} ^ { 3 }\) in volume. The number of each item to be packed, their dimensions and weights are given in the table below. Jill tries to pack the items by weight using the first-fit decreasing method.

1. List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible. Jack tries to pack the items by volume using the first-fit decreasing method.
2. List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
3. Give another reason why a packing may not be possible.

1

1. Use shuttle sort to put this list of values into decreasing order (from largest to smallest). $$\begin{array} { l l l l l l l l l } 18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22 \end{array}$$ Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
2. The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
3. Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.

1

1. 1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
   2. Find a packing that uses fewer bags.
2. The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

1

1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$

1. Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
2. Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
3. Find a way to pack the boxes into the van so that she makes as few deliveries as possible.

2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$

1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
2. Write down the two possibilities for the original list.
3. Write down the list after the second pass through the shuttle sort algorithm.
4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .

2 Two hikers each have a 25 litre rucksack to pack. The items to be packed have volumes of 14, 6, 11, 9 and 6 litres.

1. Apply the first fit algorithm to the items in the order given and comment on the outcome.
2. Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks.
3. The hikers argue that the first fit decreasing algorithm does not produce a fair allocation of volumes to rucksacks. Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing.

5

1. The following instructions operate on positive integers greater than 4.
   Step 10 Choose any positive integer greater than 4, and call it \(n\).
   Step 15 Write down \(n\).
   Step 20 If \(n\) is even then let \(n = \frac { n } { 2 }\) and write down the result.
   Step 30 If \(n\) is odd then let \(n = 3 n + 1\) and write down the result.
   Step 40 Go to Step 20.
   1. Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
   2. Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
   3. Add an instruction to stop the process when \(n\) becomes 1 .
   4. It is not known if, when modified to stop cycling through \(4,2,1\), the instructions form an algorithm. What would need to be known for it to be an algorithm?
2. Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .

   Item	A	B	C	D	E	F
   Weight \(( \mathrm { kg } )\)	2	1	6	3	3	5

   The first-fit algorithm is as follows. \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
   1. Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
   2. Place the items in increasing order of weight, and then apply the first-fit algorithm.
   3. Place the items in decreasing order of weight, and then apply the first-fit algorithm. An optimal solution is one which uses the least number of boxes.
   4. Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
   5. First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?

2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.

2. This question should be answered on the sheet provided. A builder is going to put up houses on a plot of land of area \(12000 \mathrm {~m} ^ { 2 }\).
There are 5 designs to choose from and no more than one of each design can be built. The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds \(12000 \mathrm {~m} ^ { 2 }\).

1. 1. Complete the tree diagram so that each branch is terminated or all choices have been considered.
   2. Hence, determine which designs the builder should use and the total value that the site will have when completed.
2. Explain how this method could be altered if more than one of each design is allowed.

1. The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.

$$\begin{array} { l l l l l l l l l l l l } 6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8 \end{array}$$

1. Considering only the total amount, what is the least number of rolls that are needed?
2. Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.
3. Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).
4. Comment on this result.

2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students. Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   2	4	0	2	3
   4	2	0	1	1
   5	0	1	\(k\)	0
   1	1	0	4	2
   0	2	0	0	3

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
4. Find the minimum possible total of penalty points.
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}

2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below. Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.

1. By reducing the columns first and then the rows, show that the new table of values is

   3	1	0	4	1
   0	\(k\)	0	1	3
   1	0	3	1	2
   2	3	2	0	0
   0	5	1	2	1

   State the value of the constant \(k\).
2. 1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
   2. Use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
4. Find the minimum total time for completing the five puzzles.
5. Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.

3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\). Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.

1. By reducing the columns first, and then the rows, show that the new table of values is

   0	12	13	2	0
   14	21	0	\(k\)	9
   3	10	0	6	23
   0	2	6	20	0
   0	0	0	0	7

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
4. Find the minimum total time.

1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.

Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)

5. An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below. Use the Hungarian algorithm, reducing rows first, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time.

3. Talkalot College holds an induction meeting for new students. The meeting consists of four talks: I (Welcome), II (Options and Facilities), III (Study Tips) and IV (Planning for Success). The four department heads, Clive, Julie, Nicky and Steve, deliver one of these talks each. The talks are delivered consecutively and there are no breaks between talks. The meeting starts at 10 a.m. and ends when all four talks have been delivered. The time, in minutes, each department head takes to deliver each talk is given in the table below.

1. Use the Hungarian algorithm to find the earliest time that the meeting could end. You must make your method clear and show
   1. the state of the table after each stage in the algorithm,
   2. the final allocation.
2. Modify the table so it could be used to find the latest time that the meeting could end.

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.

Worker A cannot do task 4 and worker B cannot do task 2. The amount, in pounds, that each worker would earn if assigned to the tasks, is shown in the table below. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.

5. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of three sales points, \(\mathrm { P } , \mathrm { Q }\) and R . It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required. The north-west corner method gives the following initial solution.

1. Taking AQ as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
2. Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal. Justify your answer.
4. State the cost of the solution you found in (b).
5. Formulate this problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

3. Four pupils, Alexa, Ewan, Faith and Zak, are to be allocated to four rounds, 1, 2, 3 and 4, in a mathematics competition. Each pupil is to be allocated to exactly one round and each round must be allocated to exactly one pupil. Each pupil has been given a score, based on previous performance, to show how suitable they are for each round. The higher the score the more suitable the pupil is for that round. The scores for each pupil are shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total score. You must make your method clear and show the table after each stage.
   (8)
2. State the maximum total score.

5. The table below shows the cost of transporting one unit of stock from each of four supply points, 1 , 2,3 and 4, to each of three demand points, A, B and C. It also shows the stock held at each supply point and the stock required at each demand point. A minimal cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. Add a dummy demand point and appropriate values to Table 1 in the answer book.
3. Use the north-west corner method to obtain a possible solution. After one iteration of the stepping-stone method the table becomes

   	A	B	C	D
   1	15
   2	19	17
   3		3	25
   4	6			14

4. Taking D3 as the entering cell, use the stepping-stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
5. Determine whether your solution from (d) is optimal. Justify your answer.

1. A company has five machines \(A , B , C , D\) and \(E\), which it can assign to four tasks \(1,2,3\) and 4 . Each task must be assigned to just one machine and each machine may only be assigned to just one task.

The profit, in \(\pounds 100\) s, of using each machine to do each task is given in the table below.

1. Explain why it is necessary to add a dummy column to the table.
   (2)
2. Use the Hungarian algorithm to allocate machines to tasks in order to maximise the total profit. You must make your method clear and show the state of the table after each iteration.
   (7)
   (Total 9 marks)

2 Dudley has three daughters who are all planning to get married next year. The girls are named April, May and June, after the months in which they were born. Each girl wants to get married on her own birthday. Dudley has already obtained costings from four different hotels. From past experience, Dudley knows that when his family get together they are likely to end up with everyone fighting one another, so he cannot use the same hotel twice. The table shows the costs, in \(\pounds 100\), for each hotel to host each daughter's wedding. Dudley wants to choose the three hotels to minimise the total cost.
Add a dummy row and then apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the hotels and Dudley's daughters. State how each table is formed and write out the final solution and its cost to Dudley.

2 Amir, Bex, Cerys and Duncan all have birthdays in January. To save money they have decided that they will each buy a present for just one of the others, so that each person buys one present and receives one present. Four slips of paper with their names on are put into a hat and each person chooses one of them. They do not tell the others whose name they have chosen and, fortunately, nobody chooses their own name. The table shows the cost, in \(\pounds\), of the present that each person would buy for each of the others. As it happens, the names are chosen in such a way that the total cost of the presents is minimised.
Assign the cost \(\pounds 25\) to each of the missing entries in the table and then apply the Hungarian algorithm, reducing rows first, to find which name each person chose.