Discrete Math, Task Scheduling

How much time is required for the critical path of the tasks shown the digraph above?

• 19

• 21

• 23

• 24

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

3 minutes, 5 minutes, 8 minutes,

4 minutes, 6 minutes, 1 minute

How much time does the resulting schedule require?

• P₁: 13; P₂: 14

• P₁: 14; P₂: 13

• P₁: 16; P₂: 11

• P₁: 15; P₂: 11

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

8 minutes, 9 minutes, 11 minutes,

3 minutes, 4 minutes, 12 minutes

How much time does the resulting schedule require?

• P₁: 15; P₂: 15, P₃: 17

• P₁: 17; P₂: 15, P₃: 15

• P₁: 20; P₂: 16, P₃: 12

• P₁: 11; P₂: 13, P₃: 23

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

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

• True

• False

Critical path scheduling is guaranteed to always produce an optimal solution, given sufficient processors.

• True

• False