Classic Bin Packing (BP) considers the task of packing a collection of items j = 1,c, n of varying sizes aj into a minimum number N of bins of capacity

b. The first-fit algorithm to solve instances approximately begins with no bins open. Then it takes items in arbitrary sequence, considering possible bins for each in the order they were opened. The item is placed in the the first bin that can accomodate it, or if none does, a new bin is opened and the item placed there.

(a) Taking items in subscript sequence, apply this first-fit heuristic to an instance with n = 12 items of sizes aj = 12, 14, 9, 19, 2, 4, 13, 8, 8, 10, 13, and 7 and bins of capacity b = 30.

(b) Justify the greedy standard of taking items in first-fit sequence.

(c) Explain why aj aj>b is a lower bound on the optimal number of bins needed in any solution, and compare to your result of part (a).

(d) Explain why there can never be more than one bin … half full at any point in the execution of the algorithm, so that the final number NQ of bins it uses must satisfy 1NQ - 121b>22 6 aj aj.

(e) Combine

(c) and

(d) to establish that the number of bins used by the first-fit heuristic solution can be no worse than twice optimal.