1. What is the minimum time required to complete 8 independent tasks with a total task time of 72 minutes on 4 machines?

2. If the list-processing algorithm is applied to the accompanying order-requirement digraph (task time in minutes) using the list T₁, T₂, T₃, T₄, and three machines are available, the earliest completion time for all the tasks is ______________.

3. The following digraph cannot be an order-requirement digraph because

4. The shortest path and longest path, respectively, in the accompanying task-analysis digraph have, respectively, lengths

5. Given the accompanying order-requirement digraph (time in minutes) and the priority list T₆, T₅, T₄, T₃, T₂, T₁, apply the list-processing algorithm to construct a schedule using two processors. The completion time of the resulting schedule is __________________________.

6. The subscripts for the tasks that make up a critical path for the order-requirement digraph below are _________,_________,_________.

7. Suppose that a crew can complete in a minimum amount of time the job whose order-requirement digraph is shown below. If task T₂ is shortened from 5 minutes to 1 minute, then the maximum amount by which the completion time for the entire job can be shortened is _________________________.

8. Suppose that independent tasks require a total of 30 minutes, while only one task takes as long as 10 minutes. If these tasks are scheduled on two machines, they

9. Which statement about the accompanying digraph is true?

10. The tasks that require the shortest and longest time to carry out in the task-analysis digraph below are, respectively, __________ and __________.

11. Assume an order-requirement digraph has a critical path with length 30 minutes. Based on this information, when the tasks are scheduled on two machines, how much time will be required?

12. The subscripts for the tasks in a critical path list associated with the following order-requirement digraph are _________,_________,_________.

13. Assume that a job consists of six independent tasks ranging in time from 2 to 10 minutes and totaling 27 minutes. Efficiently scheduled on three machines, how much time will the job require?

14. The list-processing algorithm is used to schedule independent tasks lasting 6, 7, 4, 3, and 6 minutes on three machines, using these times as given for a list. The completion time for all the tasks will be _______________.

15. A radio announcer has 10 songs of various lengths to schedule into several segments. The announcer must identify the station at least once every 15 minutes, so the segments cannot be longer than 15 minutes. This job can be solved using the

16. When the decreasing-time-list algorithm is used to schedule independent tasks lasting 6 minutes, 7 minutes, 4 minutes, 3 minutes, and 6 minutes, on two machines, a schedule results where the tasks are completed after __________ minutes.

17. When the bins have capacity 5, the next-fit (NF) bin-packing algorithm applied to the list 3, 2, 4, 1, 1, 4, 4 uses

18. Six items of size 9, five items of size 7, four items of size 6, three items of size 5, and two items of size 9 are to be packed into bins of capacity 11. The smallest number of bins that this can be accomplished with is _______________.

19. Use the worst-fit-decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 10 lb: 6 lb, 7 lb, 4 lb, 3 lb, 6 lb. How many bins are holding a full 10 lb?

20. Use the first-fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 10 lb: 6 lb, 7 lb, 4 lb, 3 lb, 6 lb. The number of bins required is _____________________.

21. When the bins have capacity 5, the next-fit decreasing (NFD) bin-packing algorithm when applied to the list 3, 2, 4, 1, 1, 4, 4 uses

22. When the bins have capacity 5, the items packed in the second bin (listed from top to bottom) using the list 3, 2, 4, 1, 1, 4, 4 by the first-fit (FF) bin-packing algorithm will be _________ and _________.

23. When the bins have capacity 5, the best-fit bin-packing algorithm applied to the list 2, 4, 1, 4, 3 packs which items in the second bin (listed from top to bottom)?

24. The first-fit-decreasing (FFD) bin-packing algorithm is applied to the weight list 1, 2, 3, 4, 5, 5, 6, 8 for packing into bins of capacity 10. The item of weight 2 is packed into the bin numbered _________ when the packed bins are numbered from left to right.

25. A vertex coloring seeks to color the vertices of a graph to ensure which of the following traits?

26. Which of the following statements is true?

27. Assume the 8 corners of a cube represent vertices of a graph and the 12 edges of a cube represent the cube’s edges. The chromatic number of this graph is _________________________.

28. Graphs that have circuits of only even lengths have chromatic number ________.

29. The minimum number of colors needed to color the vertices of the accompanying graph is

30. A graph that has a circuit of length 3 can always be vertex colored with no fewer than ________ colors.