Question 3.99

69. A data entry group must handle 30 (independent) tasks that will take the following amounts of time (in minutes) to type: 25, 18, 13, 19, 30, 32, 12, 36, 25, 17, 18, 26, 12, 15, 31, 18, 15, 18, 16, 19, 30, 12, 16, 15, 24, 16, 27, 18, 9, 14. Use these times as a priority list.

  1. Use the list-processing algorithm to find the completion time for scheduling tasks with four secretaries. Also, solve with five secretaries.
  2. Repeat the scheduling using the decreasing-time-list algorithm.
  3. Can you show that any of the schedules you get are optimal?

    Say the typing needs to be finished in 1 hour.

  4. Use the FFD heuristic to find how many typists are needed.
  5. Repeat for the NFD and WFD heuristics.
  6. Can you show that any of the solutions you get are optimal?

69.

(a) 152 min; 124 min

(b) 155 min; 120 min

(c) Yes; five-processor decreasing-time schedule

(d) 11

(e) NFD: 13; WFD: 11

(f) An optimal packing with 10 bins exists.