Exam Review Suggestions
•	Find critical path(s) for an order requirement digraph.
•	What is significant about the critical path?
•	If a critical task is shortened by x units, does the project completion time have to be shortened by x units? Explain.
•	Know how to schedule tasks on a set of processors using the list-processing algorithm.
•	What are two limiting factors on lengths of schedules?
•	Know how to use critical path to develop a priority list.
•	Know how decreasing-time lists and independent tasks relate to scheduling. 
•	Know how to use the NF, FF, WF, NFD, FFD, and WFD algorithms.
•	Know how to color vertices of a graph; know what the chromatic number is.
•	Know how to use the vertex coloring technique in resolving conflicts.

Sample Problems

1. What is the earliest completion time for this order requirement digraph? Expain your answer.

2. a. Schedule the tasks given in the order-requirement digraph below using the list-processing algorithm on two machines with the priority list.

b. Is the schedule you obtained in part a optimal? Clearly explain your answer.

3. Use the critical path scheduling and the order requirement digraph given to schedule the tasks on 3 processors.

Critical path: T2T4T5 (length 17). 

4. For the order requirement digraph given to the right:

a. Find a critical path.

b. What is the minimal completion time?  (Assume an unlimited number of machines.)

c. What happens to the minimum completion time if the completion time for task is reduced to 2 units? (Again, assume an unlimited number of machines.)  Explain.

5.  Given the following order requirement digraph.

Use the list-processing algorithm to schedule the tasks on two processors with the priority list: T1, T2, T3, T4, T7, T5, T6, T8 

6. 10 foot boards must be cut into the following lengths:
		7, 4, 8, 5, 2, 2, 6, 6, 3, 1, 9
Show the results of using the given algorithm to cut the boards.

a. next-fit 						b. first fit

c. worst fit decreasing

7. Use the indicated algorithms to pack the weights 7, 8, 3, 6, 4, 8, 2, 1 into bags that can hold a maximum of 12 pounds. How many bins are needed in each case?

a) next-fit                                          b) worst fit decreasing

8. The owner of a pet store wants to put seven dogs into pens. The following table shows an X whenever the two dogs cannot be stored in the same pen
	A	B	C	D	E	F	G	
A		X	X	X				
B	X			X	X			
C	X					X		
D	X	X				X	X	
E		X					X	
F			X	X			X	
G				X	X	X		

a. Draw a graph to represent these restrictions.

b. Use the method of vertex coloring to find the minimum number of pens the pet store owner will need.