Scroll to Top

Virtual Math Learning Center

Virtual Math Learning Center Texas A&M University Virtual Math Learning Center

Section 3.1 - Scheduling Tasks

Instructions

  • The first video below explains the concepts in this section.
  • This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.

Concepts

  • Machine scheduling problems for tasks
  • Order-requirement digraphs with priority lists
  • List processing algorithm for assigning tasks to processors

If you would like to see more videos on the topic, click the following link and check the related videos.

Exercises

Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.

1. Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \(T_8, T_7, T_6, T_5, T_4, T_3, T_2, T_1\)

An order-requirement digraph with eight tasks

Completion Time: 13 minutes

If you would like to see more videos on this topic, click the following link and check the related videos.

2. Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \(T_1, T_2, T_3, T_4, T_5, T_6, T_7, T_8\)

An order-requirement digraph with eight tasks

Completion Time: 11 min.

If you would like to see more videos on this topic, click the following link and check the related videos.

3. Use the list processing algorithm to find the completion time using 3 processors given the following priority list: \(T_1, T_2, T_3, T_4, T_5, T_6, T_7, T_8\)

An order-requirement digraph with eight tasks

Completion Time: 12 minutes

If you would like to see more videos on this topic, click the following link and check the related videos.

4.

Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \(T_3,\) \(T_7,\) \(T_9,\) \(T_5,\) \(T_8,\) \(T_6,\) \(T_{10},\) \(T_{12},\) \(T_2,\) \(T_{11},\) \(T_1,\) \(T_4,\)

An order-requirement digraph with twelve tasks

Completion Time: 51 minutes

If you would like to see more videos on this topic, click the following link and check the related videos.

5. Use the list processing algorithm to find the completion time using 3 processors given the following priority list: \(T_3,\) \(T_7,\) \(T_9,\) \(T_5,\) \(T_8,\) \(T_6,\) \(T_{10},\) \(T_{12},\) \(T_2,\) \(T_{11},\) \(T_1,\) \(T_4,\)

An order-requirement digraph with twelve tasks

Completion Time: 47 minutes

If you would like to see more videos on this topic, click the following link and check the related videos.

6. Use the list processing algorithm to find the completion time using 3 processors given the following priority list: \(T_1,\) \(T_4,\) \(T_{11},\) \(T_6,\) \(T_7,\) \(T_3,\) \(T_{12},\) \(T_2,\) \(T_{10},\) \(T_5,\) \(T_8,\) \(T_9\)

An order-requirement digraph with twelve tasks

Completion Time: 44 minutes

If you would like to see more videos on this topic, click the following link and check the related videos.

7. Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \(T_{4},\) \(T_{3},\) \(T_{7},\) \(T_{1},\) \(T_{6},\) \(T_{5},\) \(T_{2},\) \(T_{8}.\) Is the schedule optimal?

An order-requirement digraph with eight tasks

Video Errata: At 5:20, the presenter says the critical path ends with \(T_8\), but it should end at \(T_7\).

Completion Time: 22 minutes
Yes, it is optimal since the critical path is 22 minutes.

If you would like to see more videos on this topic, click the following link and check the related videos.

8. Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \( T_{1},\) \( T_{2},\) \( T_{3},\) \( T_{4},\) \( T_{5},\) \( T_{6},\) \( T_{7},\) \( T_{8},\) \( T_{9}.\) Is the schedule optimal?

An order-requirement digraph with nine tasks

Completion Time: 27 minutes
No, it is not optimal since the critical path is 20 minutes.

If you would like to see more videos on this topic, click the following link and check the related videos.

9. Use the list processing algorithm to find the completion time using 2 processors given the following priority list: \(T_{9},\) \(T_{5},\) \(T_{2},\) \(T_{4},\) \(T_{3},\) \(T_{6},\) \(T_{8},\) \(T_{1},\) \(T_{7}.\) Is the schedule optimal?

An order-requirement digraph with nine tasks

Completion time: 22 minutes
No, it is not optimal since the critical path is 21 minutes.

If you would like to see more videos on this topic, click the following link and check the related videos.

10. Use the list processing algorithm to find the completion time using 3 processors given the following priority list: \(T_{9},\) \(T_{5},\) \(T_{2},\) \(T_{4},\) \(T_{3},\) \(T_{6},\) \(T_{8},\) \(T_{1},\) \(T_{7}.\) Is the schedule optimal?

An order-requirement digraph with nine tasks

Completion Time: 21 minutes
Yes, this schedule is optimal since the critical path is also 21 minutes. 

If you would like to see more videos on this topic, click the following link and check the related videos.

11. Find the critical path. Use the list processing algorithm to find the completion time using 3 processors given the following priority list: \(T_{8},\) \(T_{7},\) \(T_{6},\) \(T_{5},\) \(T_{4},\) \(T_{3},\) \(T_{2},\) \(T_{1},\)

An order-requirement digraph with eight tasks

Critical Path: \(T_5\) \(T_7\) \(T_8\) 
Completion Time: 21 minutes
Note, this is not an optimal schedule since the completion time is longer than the critical path.
 

If you would like to see more videos on this topic, click the following link and check the related videos.

Change the section

Prev Section Next Section Return to Course