Math Problem Statement

Use the decreasing time algorithm to create a priority list for the digraph below, then schedule the project with two processors.

T1 (9)T2 (2)T3 (12)T4 (7)T5 (5)T6 (6)T7 (5)T8 (5)T9 (8)End[Graphs generated by this script: setBorder(60,30,60,30);initPicture(0,3,0,2); fontsize=14;fontstyle='none';marker="arrow";line([0,2],[1,1]);line([0,1],[1,1]);line([0,1],[1,0]);line([0,0],[1,1]);line([1,2],[2,2]);line([1,2],[2,1]);line([1,1],[2,2]);line([1,1],[2,1]);line([1,1],[2,0]);line([1,0],[2,1]);line([1,0],[2,0]);line([2,2],[3,1]);line([2,1],[3,1]);line([2,0],[3,1]);fontbackground='white';fontfill='blue';text([0,2],'T1 (9)','aboveleft');dot([0,2]);fontfill='blue';text([0,1],'T2 (2)','belowleft');dot([0,1]);fontfill='blue';text([0,0],'T3 (12)','belowleft');dot([0,0]);fontfill='blue';text([1,2],'T4 (7)','aboveleft');dot([1,2]);fontfill='blue';text([1,1],'T5 (5)','belowleft');dot([1,1]);fontfill='blue';text([1,0],'T6 (6)','belowleft');dot([1,0]);fontfill='blue';text([2,2],'T7 (5)','aboveright');dot([2,2]);fontfill='blue';text([2,1],'T8 (5)','belowright');dot([2,1]);fontfill='blue';text([2,0],'T9 (8)','belowright');dot([2,0]);fontfill='blue';text([3,1],'End','belowright');dot([3,1]);]

Task 5 is done by Select an answer Processor 1 Processor 2 Correct starting at time 

Task 6 is done by Select an answer Processor 1 Processor 2 Correct starting at time 

The finishing time for the schedule is 

Solution

To solve this problem using the decreasing time algorithm with two processors, we will follow these steps:

  1. Create the Priority List Using Decreasing Time Algorithm:

    • First, we list all tasks in descending order based on their duration.
    • Then, we respect the task dependencies (as indicated by the graph) when scheduling.
  2. Assign Tasks to Processors and Calculate Starting and Finishing Times:

    • We assign tasks to processors based on their availability and the priority list.

Step 1: Create the Priority List

The tasks are as follows:

  • T3 (12 units)
  • T1 (9 units)
  • T9 (8 units)
  • T4 (7 units)
  • T6 (6 units)
  • T5 (5 units)
  • T7 (5 units)
  • T8 (5 units)
  • T2 (2 units)

Priority List in Decreasing Order:

  • T3 (12)
  • T1 (9)
  • T9 (8)
  • T4 (7)
  • T6 (6)
  • T5 (5)
  • T7 (5)
  • T8 (5)
  • T2 (2)

Step 2: Assign Tasks to Processors

  1. T3 (12 units):

    • This is the highest priority task, so it is assigned to Processor 1 starting at time 0.
  2. T1 (9 units):

    • This task is assigned to Processor 2 starting at time 0.
  3. T9 (8 units):

    • Processor 1 will be available after T3 completes at time 12, so T9 can start on Processor 1 at time 12.
  4. T4 (7 units):

    • Processor 2 will be available after T1 completes at time 9, so T4 can start on Processor 2 at time 9.
  5. T6 (6 units):

    • Processor 2 will be available after T4 completes at time 16, so T6 can start on Processor 2 at time 16.
  6. T5 (5 units):

    • Processor 1 will be available after T9 completes at time 20, so T5 can start on Processor 1 at time 20.
  7. T7 (5 units):

    • Processor 2 will be available after T6 completes at time 22, so T7 can start on Processor 2 at time 22.
  8. T8 (5 units):

    • Processor 1 will be available after T5 completes at time 25, so T8 can start on Processor 1 at time 25.
  9. T2 (2 units):

    • Processor 2 will be available after T7 completes at time 27, so T2 can start on Processor 2 at time 27.

Summary of Scheduling

  • Processor 1:

    • T3: Start at 0, End at 12
    • T9: Start at 12, End at 20
    • T5: Start at 20, End at 25
    • T8: Start at 25, End at 30
  • Processor 2:

    • T1: Start at 0, End at 9
    • T4: Start at 9, End at 16
    • T6: Start at 16, End at 22
    • T7: Start at 22, End at 27
    • T2: Start at 27, End at 29

Answers to the Specific Questions:

  • Task 5 is done by: Processor 1, starting at time 20.
  • Task 6 is done by: Processor 2, starting at time 16.
  • The finishing time for the schedule is: 30 units.

Would you like more details on how this was calculated, or do you have any further questions?


Here are 8 related questions to expand your understanding:

  1. How would the schedule change if we added a third processor?
  2. What are some advantages of using the decreasing time algorithm in scheduling?
  3. How do dependencies between tasks impact the final schedule?
  4. Can this method be adapted for real-time task scheduling?
  5. What happens if two tasks with the same duration but different dependencies are next in line for scheduling?
  6. How does task preemption affect the scheduling strategy?
  7. What are potential challenges in scheduling when tasks have variable processing times?
  8. How would the schedule be affected if task T3 had a higher dependency?

Tip: In scheduling problems, consider both task duration and dependencies to ensure that the final schedule is efficient and meets all constraints.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Scheduling Algorithms
Task Dependency Graphs
Processor Allocation

Formulas

-

Theorems

-

Suitable Grade Level

Advanced Undergraduate