Discrete Math - Ch 3: Task Scheduling

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?

• 14

• 15

• 16

• 18

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?

• 40

• 44

• 45

• 49

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

• 21

• 22

• 23

• 24

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?

• 6

• 14

• 24

• 42

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

• 2

• 8

• 16

• 18

Use the decreasing-time-list algorithm to schedule these tasks on two machines:

3 minutes, 5 minutes, 8 minutes,

4 minutes, 6 minutes, 2 minutes

How much time does the resulting schedule require?

• 14

• 15

• 16

• 18

Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below. If Task T₂ is shortened from 9 minutes to 6 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

• It cannot be reduced.

• 1 minute

• 2 minutes

• 3 minutes

Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below. If Task T₅ is shortened from 6 minutes to 3 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

• It cannot be reduced.

• 1 minute

• 2 minutes

• 3 minutes

What is the minimum time required to complete eight independent tasks with a total task time of 160 minutes on four machines?

• 10 minutes

• 20 minutes

• 40 minutes

• 60 minutes

When scheduling tasks using the list-processing algorithm, increasing the number of machines always reduces the completion time.

• True

• False