Deck 3: Planning and Scheduling

Question 1

Apply the list-processing algorithm to construct a schedule using three processors.

Answer 1

Question 2

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

Answer 2

FF. One can pack as tightly as needed.

Question 3

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

Answer 3

Answers may vary. One example is: When the capacity is 10 lbs, the weights are 7 lbs, 6 lbs, 5 lbs, and 5 lbs.

Question 4

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

Question 5

Give an example of an order-requirement digraph with six tasks T₁, T₂, T ₃, T₄, T₅, T₆ that requires 10 minutes when scheduled on two processors.

Question 6

For a scheduling problem, list at least three possible goals to achieve.

Question 7

Apply the list-processing algorithm to construct a schedule using two processors.

Question 8

Apply the critical-path scheduling algorithm to construct a schedule using three processors.

Question 9

Give an example of an order-requirement digraph with six tasks T₁, T₂, T ₃, T₄, T₅, T₆ for which the critical-path is T₁, T₃, T₄.

Question 10

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

Question 11

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?

Question 12

What is the minimum number of processors required to complete eight independent tasks in 40 minutes when the sum of the times of the eight tasks is 120 minutes?

Question 13

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?

Question 14

Apply the critical-path scheduling algorithm to construct a schedule using two processors.

Question 15

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

Question 16

For an order-requirement digraph of 10 tasks, how many priority lists are possible?

Question 17

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?

Question 18

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

Question 19

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

Question 20

A talent show producer needs to fit 17 acts of varying lengths into three segments. The segments should be as short as possible and are to be separated by intermissions. How can this problem be solved?

Question 21

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₄, T ₅, T₂, T₃, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 14 minutes
B) 15 minutes
C) 16 minutes
D) 18 minutes

Question 22

Find the chromatic number of the graph below:

Question 23

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 14 minutes
B) 15 minutes
C) 16 minutes
D) 18 minutes

Question 24

What is the chromatic number of the complete graph on six vertices?

Question 25

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?

Question 26

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

Question 27

Apply the list-processing algorithm to construct a schedule using two processors.

Question 28

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 15 minutes
B) 16 minutes
C) 17 minutes
D) 18 minutes

Question 29

Find the chromatic number of the graph below:

Question 30

Apply the critical-path scheduling algorithm to construct a schedule using three processors.

Question 31

Find the chromatic number of the graph below:

Question 32

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 21 minutes
B) 22 minutes
C) 23 minutes
D) 24 minutes

Question 33

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

Question 34

Apply the list-processing algorithm to construct a schedule using three processors.

Question 35

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, T₇, T₈, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 40 minutes
B) 44 minutes
C) 45 minutes
D) 49 minutes

Question 36

Compare the first-fit (FF) and first-fit decreasing (FFD) bin-packing algorithms in packing the following weights into bins that can hold no more than 10 lbs. 3 lb, 8 lbs, 5 lbs, 7 lbs, 5 lbs, 5 lbs, 8 lbs, 4 lbs, 10 lbs, 6 lbs

Question 37

Use the decreasing-time-list algorithm to schedule these tasks on two machines:
4, 2, 1, 6, 4, 5, 4 (time in minutes).
How much time does the resulting schedule require?

Question 38

Apply the critical-path scheduling algorithm to construct a schedule using two processors.

Question 39

Find the chromatic number of the graph below:

Question 40

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, T₇, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 16 minutes
B) 17 minutes
C) 18 minutes
D) 21 minutes

Question 41

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the worst-fit (WF) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 42

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the first-fit (FF) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 43

Given the order-requirement digraph below (with time given in minutes), apply the critical-path scheduling algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 15 minutes
B) 16 minutes
C) 17 minutes
D) 18 minutes

Question 44

What is the minimum number of machines required to perform eight independent tasks in 12 minutes with a total task time of 48 minutes?

A) 4
B) 5
C) 6
D) 8

Question 45

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require?

A) 17 minutes
B) 18 minutes
C) 19 minutes
D) 22 minutes

Question 46

Given the order-requirement digraph below (with time given in minutes), apply the critical-path scheduling algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 14 minutes
B) 15 minutes
C) 16 minutes
D) 18 minutes

Question 47

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the next-fit decreasing (NFD) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 48

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the next-fit (NF) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 49

What is the minimum time required to complete the following tasks on two processors?

A) 15 minutes
B) 16 minutes
C) 17 minutes
D) 18 minutes

Question 50

Given the order-requirement digraph below (with time given in minutes), apply the critical-path scheduling algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 21 minutes
B) 22 minutes
C) 23 minutes
D) 24 minutes

Question 51

Given the order-requirement digraph below (with time given in minutes), apply the critical-path scheduling algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 40 minutes
B) 44 minutes
C) 45 minutes
D) 49 minutes

Question 52

Given the order-requirement digraph below (with time given in minutes), apply the critical-path scheduling algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 16 minutes
B) 17 minutes
C) 18 minutes
D) 21 minutes

Question 53

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₄, T ₅, T₂, T₃, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

A) 21 minutes
B) 22 minutes
C) 23 minutes
D) 24 minutes

Question 54

What is the minimum number of processors required to perform the following tasks in 12 minutes?

A) 2
B) 3
C) 4
D) 5

Question 55

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require?

A) 19 minutes
B) 20 minutes
C) 21 minutes
D) 22 minutes

Question 56

What is the minimum time required to complete nine independent tasks on three processors when the sum of all the times of the nine tasks is 72 minutes?

A) 3 minutes
B) 8 minutes
C) 24 minutes
D) 27 minutes

Question 57

What is the minimum number of machines required to perform six independent tasks in 16 minutes with a total task time of 48 minutes?

A) 2
B) 3
C) 4
D) 6

Question 58

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

A) 4 minutes
B) 9 minutes
C) 16 minutes
D) 36 minutes

Question 59

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require?

A) 14 minutes
B) 15 minutes
C) 16 minutes
D) 17 minutes

Question 60

What is the minimum time required to complete 12 independent tasks on two processors when the sum of all the times of the 12 tasks is 84 minutes?

A) 6 minutes
B) 14 minutes
C) 24 minutes
D) 42 minutes

Question 61

Choose the packing that results from the use of the first-fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
d. Another packing

Question 62

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the first-fit decreasing (FFD) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 63

Choose the packing that results from the use of the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. 5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs

A)
B)
C)
D) Another packing

Question 64

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

A)
B)
C)
D)

Question 65

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

A)
B)
C)
D)

Question 66

Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 67

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
Find the number of bins required using the worst-fit decreasing (WFD) algorithm.

A) 4
B) 5
C) 6
D) 8

Question 68

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

A)
B)
C)
D) Another packing

Question 69

Choose the packing that results from the use of the worst-fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 70

Choose the packing that results from the use of the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
D) Another packing

Question 71

Choose the packing that results from the use of the next-fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 72

Choose the packing that results from the use of the worst-fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
D) Another packing

Question 73

Choose the packing that results from the use of the first-fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 74

Choose the packing that results from the use of the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 75

Choose the packing that results from the use of the first-fit decreasing (FFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
D) Another packing

Question 76

Choose the packing that results from the use of the next-fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
D) Another packing

Question 77

Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. 5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs

A)
B)
C)
D) Another packing

Question 78

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

A)
B)
C)
D)

Question 79

Choose the packing that results from the use of the first-fit decreasing (FFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.

A)
B)
C)
D)

Question 80

Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.

A)
B)
C)
D) Another packing