Question 3.129

99.

  1. Given items with weights 3, 9, 6, 5, 3, 1, 7, 4, 5, 6, determine the number of bins (advertising break slots) in which to pack these items if the bin size is 10 using first fit, next fit, and first-fit decreasing.
  2. If we interpret these weights as times for independent tasks to be scheduled on machines, what would be the earliest completion time for these tasks scheduled on 3 machines, using the given list?
  3. If in part (b) we use the decreasing-time list, what is the earliest completion time?
  4. Is your answer in part (c) optimal?

99.

(a) Contents of bins listed as items from the bottom to the top: First fit: Bin 1: 3, 6, 1; Bin 2: 9; Bin 3: 5, 3; Bin 4: 7; Bin 5: 4, 5; Bin 6: 6. Next fit: Bin 1: 3; Bin 2: 9; Bin 3: 6; Bin 4: 5, 3, 1; Bin 5: 7; Bin 6: 4, 5; Bin 7: 6. First-fit decreasing: Bin 1: 9, 1; Bin 2: 3, 7; Bin 3: 6, 4; Bin 4: 6, 3; Bin 5: 5, 5.

(b) 19

(c) 17

(d) Yes