1.	Which of the algorithms:  first fit (FF), next fit (NF), or worst fit (WF) would be most preferable when filling boxes on an assembly line?  Why? 	

2.	Which of the algorithms:  first fit (FF), next fit (NF), or worst fit (WF) would be most preferable when packing cloth dolls?  Why? 	

3.	Which of the algorithms:  first fit (FF), next fit (NF), or worst fit (WF) would be most preferable when packing china dishes?  Why? 	

4.	Which of the algorithms:  first fit (FF), next fit (NF), or worst fit (WF) would be most preferable when cutting wooden shelves from planks?  Why? 	

5.	Which of the algorithms:  first fit (FF), next fit (NF), or worst fit (WF) would be most preferable when cutting quilt pieces?  Why? 	

6.	Use the first fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs	

7.	Use the next fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs 	

8.	Use the worst fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs	

9.	Use the first-fit decreasing (FFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs 	

10.	Use the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs 	

11.	Use the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs 	

12.	Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T2, T 3, T4, T5, T6, apply the list-processing algorithm to construct a schedule using two processors.

13.	Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T2, T 3, T4, T5, T6, apply the list-processing algorithm to construct a schedule using three processors.

14.	Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T2, T 3, T4, T5, T6, apply the critical-path scheduling algorithm to construct a schedule using two processors.

15.	Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T2, T 3, T4, T5, T6, apply the critical-path scheduling algorithm to construct a schedule using three processors.

16.	What is the minimum time required to complete 12 independent tasks on three processors when the sum of all the times of the 12 tasks is 60 minutes? 	

17.	What is the minimum time required to complete eight independent tasks on two processors when the sum of the times of the eight tasks is 64 minutes? 	

18.	Give an example of an order-requirement digraph with six tasks T1, T2, T 3, T4, T5, T6 for which the critical-path is T1, T3, T4.	

19.	Give an example of an order-requirement digraph with six tasks T1, T2, T 3, T4, T5, T6 that requires 10 minutes when scheduled on two processors.	

20.	Give an example in which six independent tasks require 12 minutes when scheduled on three processors. 	

21.	Give an example in which the first fit (FF) and next fit (NF) bin-packing algorithms produce the same packing. 	

22.	Give an example in which the first-fit decreasing (FFD) and worst-fit decreasing (WFD) bin-packing algorithms produce the same packing. 	

23.	Why are there several different algorithms for the bin-packing problem? 	

24.	When scheduling independent tasks, why does the decreasing-time-list algorithm generally produce good schedules?  Does it always produce an optimal schedule? 	

25.	When scheduling tasks using an order-requirement digraph, why does the critical-path scheduling algorithm generally produce good schedules?  Does it always produce an optimal schedule? 	

26.	Find the chromatic number of the graph below:

27.	Find the chromatic number of the graph below:

28.	The table below represents species of plants that have competing light or water requirements.  Draw the graph which would be useful in determining the minimum number of different habitats that would be needed to display all these plants in a garden.

A	
B	
C	
D	
E	

A	
	
X	
	
X	
X	

B	
X	
	
X	

C	
	
X	
	
X	

D	
X	
	
X	
	
X	

E	
X	

X	

29.	Use the decreasing-time list algorithm to schedule these tasks on three machines: 
7, 2, 5, 3, 9, 1, 6, 5, 3, 7
How much time does the resulting schedule require? 	

30.	Given the order requirement digraph below (with time given in minutes) and the priority list T1, T2, T3, T4, T5, T6, T7, T8, apply the critical-path scheduling algorithm to construct a schedule using two processors.

31.	Given the order requirement digraph below (with time given in minutes) and the priority list T1, T2, T3, T4, T5, T6, T7, T8, apply the critical-path scheduling algorithm to construct a schedule using three processors.

32.	Given the order requirement digraph below (with time given in minutes) and the priority list T1, T2, T3, T4, T5, T6, T7, T8, apply the list-processing algorithm to construct a schedule using two processors.

33.	Given the order requirement digraph below (with time given in minutes) and the priority list T1, T2, T3, T4, T5, T6, T7, T8, apply the list-processing algorithm to construct a schedule using three processors

34.	What is the minimum time to complete 12 independent tasks on four processors when the sum of all the times of the 12 tasks is 60 minutes? 	

Answer Key

1.	NF. One doesn't have to go back.	
2.	FF. One can pack as tightly as needed.	
3.	WF. There can be equal room in each box.	
4.	WF. This allows for some "error" or sawdust scraps.	
5.	FF. This keeps scraps large if possible.	
6.	1
2
1 1 5 6
5 7 4 3 2	
7.	
	
8.	1
2
1 1 5 6
5 7 4 3 2	
9.	
	
10.	
	
11.	
	
12.	
	
13.	
	
14.	
	
15.	
	
16.	20 minutes	
17.	32 minutes	
18.	For example,
	
19.	 For example,	
T1 (3) ® T2 (3) ® T3 (4)	

T4 (2)  T5 (6)  T2 (1)	

20.	For example, 6,6,6,6,6,6.	
21.	For example, when the capacity is 10 lbs. The weights are 7 lbs, 6 lbs, 5 lbs, and 5 lbs.	
22.	For example, when the capacity is 10 lbs. The weights are 7 lbs, 6 lbs, 5 lbs, and 5 lbs.	
23.	There are different situations and no best algorithm.	
24.	It produces good schedules because the bigger tasks are done early, allowing for smaller tasks to fill in the remaining time.	
25.	It completes "prerequisite" tasks early, but this is not always an optimal schedule.	
26.	The chromatic number is 3.	
27.	The chromatic number is 3.	
28.	Answers may vary.  One solution is given by the graph below:
	
29.	16 minutes	
30.	
	
31.	
	
32.	
	
33.	
	
34.	15 minutes