Section 8.2: Directed Graphs (Digraph)

He or She Loves Me, He or She Loves Me Not:

If we have a boy (B) and a girl (G), what are different ways that these two people might like each other.

Let’s represent this interest or lack there of in a graph. Let B and G be our boy and girl.

Directed Graph or DIGRAPH:a graph in which the edges have ______associated with them

  • Example:

Key Terms about Digraphs:

ARCS:

  • Direction = ______vertex to an ______vertex
  • XY:
  • YX:

ARC-SET:

INCIDENCE: relationship of vertices (direction of arcs)

  • A incident to B
    where are you going TO:
  • Eincident from D
    where are you FROM:

ADJACENT ARCS: starting vertex of one arc is the ending vertex of another

PATH: sequence of adjacent arcs between initial starting vertex and final ending vertex and no arc appears more than once

“Circuit in graph”; CYCLE: path that starts and ends at the ______vertex

“Degree in a graph”;

  • OUTDEGREE OF VERTEX: # of arcs for which the vertex is the ______vertex
  • INDEGREE OF VERTEX: # of arcs for which the vertex is the ______vertex

EXAMPLE OF KEY TERMS:

Example #1: Consider the digraph right

1a) A is incident to …

1b) A is incident from …

1c) Find the Indegree and Outdegree of each vertex.

d) Find a path from A to D.

1e) Do any cycles exist? If so, where?

Example #2:Consider the digraph of arc-set {VW, VZ, WZ, XY, XZ, YW, ZY, ZW}

2a) What is the outdegree of V and Z?

2b) What is the indegree of V and Z?

APPLICATIONS OF DIGRPAHS:

(1) Traffic Flow: / (3) Tournaments:
(2)Telephone Traffic: / (4) Organization/Flow Charts:

PROJECT DIGRAPH: Overall VISUAL representation of ALL TASKS and PRECENDENCE RELATIONS (prerequisites) to flow from what can be started immediately to what has to wait on others to be finished

PROJECT DIGRPAH EXAMPLES:

#1: Starting your Day: (1) Waking Up, (2) Breakfast, (3) Shower, (4) Brush Teeth,
(5) Dressed, (6) Packing School Bag, (7) Getting to School

#2. Draw a project digraph described in the tables

Task / Precedence Relations
U / X  U, Y  U
V / Y  V
W / X  W
X
Y
Task / Precedence Relations
A / C A, F A
B
C / BC, E C
D
E
F / BF
G / B G , D  G
H / F H, GH

#3: FIVE computer programs needs to be executed. There are one 10-minute, two 7-minute, one 12-minute, and one 20-minute programs. The 20-minute program requires both 7-minute programs to be finished before starting. The 10-minute program cannot be started until the 12-minute program has been completed. Draw a project digraph for this situation.

HOMEWORK: pp. 301 – 302 #2, 4, 5, 9, 11, 13, 15, 16

Section 8.1: Basic Elements of Scheduling

What do you need to do to apply to and attend college?

To “Schedule” Applying for and Attending College:

Can you do them all at once? Who can do them? How long does each thing take?

ISSUES OF SCHEDULING IN REAL-LIFE:

Basic Elements of Scheduling:(Assumptions are a simplified version of reality)

PROCESSORS:

  • Who?
  • N = number of processors
  • Notation: P1, P2, …, PN

TASKS:______ which can’t be broken up into smaller amounts/parts

  • Each task ______- between different processors
  • Notation: Capital letters represent tasks

STATES OF TASKS:

  1. COMPLETED: processor has started and ______task
  1. IN EXECUTION: processor has started and is ______working on task
  1. READY:______be started because ______prerequisites have been completed
  1. INELIGIBLE:______be started because ______number of prerequisites have not been completed

EXAMPLES: TASK OF GETTING A LICENSE

INELIGIBLE:

READY:

IN EXECUTION:

COMPLETED:

PROCESSING TIMES:

the amount of time, without interruption, required by one processor to execute the task.

3 ASSUMPTIONS ABOUT PROCESSING TIMES

  1. VERSATILITY:______processor can execute ______task
  1. UNIFORMITY: processing time for a task is the ______regardless of the processor
  1. PERSERVERANCE: processor will complete task ______
  • Notation:task X has a processing time of nunits = X(n)
  • Units can be seconds, minutes, hours, days, any measurement of time

PRECEDENCE RELATIONS:formal restrictions on order tasks can be executed.

  • Notation: X → Y
  • Graphical Representation:
  • INDEPENDENT:
  • TRANSITIVE: If X → Y and Y → Z, then X → Z
  • CYCLES: X → Y, Y → W, W → Z, Z → X

OVERALL SCHEDULING ELEMENTS EXAMPLE:Repairing a Car

Imagine you wrecked a car and need to get it fixed. According to the garage, there are 4 kinds of damages to your car the need to be repaired: Exterior Body work (4 hours), Engine (5 hours), Painting and Exterior Finishing (7 hours), and Transmission (3 hours). Two different mechanics will work to finish repairs on your car. How does this represent a scheduling problem?

Processors: / Tasks: / Precedence Relation:

FINISHING TIME (FIN): duration of project from the start of the 1st task to the completion of the last task based on schedule.

OPTIMAL TIME (OPT): shortest finishing time for the project

Optimal Schedule: a schedule (timeline) creating the optimal finishing time

Possible Schedules:

Finishing Time =

Finishing Time =

Finishing Time =

Finishing Time =

Section 8.7: Scheduling with Independent Tasks

What are INDEPENDENT TASKS?

What does the project digraph of independent tasks look like?

Example: Draw the project digraph for tasks A, B, C, D that take 5, 2, 3, 7 minutes to complete respectively.

Example SCHEDULING INDEPENDENT TASKS (SIMPLEST CASE): Find the fastest way to complete the above independent tasks (A, B, C, D) for the project with the given number of processors

  1. For 2 processors:
  1. For 3 processors:
  1. For 4 processors:

Example #2: For the given independent tasks E(4), F(5), G(2), H(6), I(7), find the fastest way to schedule

  1. For 2 processors:
  1. For 3 processors:

Example #3: For the independent tasks A(1), B(1), C(2), D(3), E(4), F(5) find the fastest way to schedule

  1. For 2 processors:
  1. For 3 processors:
  1. For 4 processors:

EXAMPLE 4:3 friends are cooking a nine-course luncheon with each course listed with processing time in minutes: A(70), B(90), C(100), D(70), E(80), F(20), G(20), H(80), I(10).Find the fastest way to schedule all tasks with 3 Processors.

4b. 180 minutes is the optimal time, why?

EXPLORATION:

  1. If you know all of the processing times and the number of processors, can you calculate a minimum number for the FIN (finishing time)?
  1. If you know all of the processing times, can you make statement of the minimum time for the FIN regardless of the number of processors you might assign?

SCHEDULING WITH INDEPENDENT TASKS:Trying to make optimal schedules

(1)All tasks are automatically READY from the start

(2)All Ready Tasks  Processors will NEVER IDLE until the END when NO tasks remain

(3)Calculate the TOTAL PROCESSING TIME DIVIDE BY PROCESSORS FIN

(4)Use the given processing times to make each processor get as close as possible to the calculated FIN time.

PRACTICE: Find the optimal schedule for the given processors and tasks.

#1:3 Processors and tasks = A(50), B(30), C(40), D(30), E(50), F(30), G(40)

#2:2 Processors and tasks: A(45), B(55), C(25), D(75), E(30), F(35), G(15)

#3:4 Processors and tasks: A(90), B(50), C(40), D(10), E(20), F(30), G(25), H(35), I(60)

#4: 3 PROCESSORS and 18 independent tasks with processing times given by
1, 2, 3, …, 17, 18.

#5: 2 PROCESSORS and 11 independent tasks with processing times of
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

#6: 2 PROCESSORS and 12 Independent tasks with processing times of
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and 144

HOMEWORK: Find Optimal Schedule and OPT for task lists given in problems p.306 #51 - 53, 55

Section 8.3: Scheduling with Priority Lists

INTRODUCTION: SCHEDULING WITH PROJECT DIGRAPH v. INDEPENDENT TASKS

  • Create at least two different schedules for 2 processors based on the given project digraph

Project Digraph #1:


Project Digraph #2:

Project Digraph #3:To launch a satellite into space, a system checks need to be performed. There are five systems to check: A(6), B(5), C(7) , D(2), and E(5) with the numbers representing the hours computer to perform that check. The following precedence relations are known: D cannot be started until A and B have finished, and E cannot be started until C has finished. Draw the project digraph.

The project digraph provides the basic graph model that describes all the information in a scheduling problem. It does ______actually tell us how to create a schedule.

PRIORITY LIST: list of all tasks prioritized based on ______to do all tasks

EXAMPLE: Priority List for tasks X and Y= {X, Y}

  • OPTION #1:If task X is ready, then ______
  • OPTION #2:If task X is not ready (ineligible), then ______
  • OPTION #3:If task X and task Y are both not ready, then ______

PRIORITY-LIST MODEL: process of scheduling tasks using a priority list

  • Number of Priority Lists in a project with M tasks is M!

Example: 5 tasks

GROUND RULES FOR PRIORITY LIST MODEL

PROCESSORS: At any moment during the project processors are either

  1. BUSY:
  2. IDLE:

STATUS OF TASKS: IneligibleReady  In Execution  Completed

3 Different Scenarios of Scheduling with Priority List:

1)ALL Processors are BUSY

2)ONE Processor is FREE:Find and complete ______task from Left to Right in Priority List

  • No Ready Task = processors must ______for new ready tasks

3)MORE THAN ONE Processor is FREE:Assign ______tasks in left to right priority to ______processors

  • Any unassigned processors must IDLE for new ready tasks
  • Any unassigned but ready tasks will not be started until new processors are available

SCHEDULING SIMPLIFIED STEPS

Step #1:PROJECT DIGRAPH

-WHAT TASKS ARE NOW READY? (all arrows leading to a task have been finished)

-IDENTIFY those tasks in priority list

Step #2:PRIORITY LIST

-What is the FIRST READY TASK in the list (read left to right)?

-Assign to first available processor in timeline/ schedule

STEP #3:TIMELINE/SCHEDULE

-If multiple tasks are ready in priority list, then you can assign to available multiple processors

-If no task is ready, processor will wait or idle until tasks next task is completed in schedule

-Cross out a task in the priority list when it is completed.

EXAMPLES OF SCHEDULING: Complete the timeline and Calculate the finish time.

1) Priority List: A(6), B(5), C(7), D(2), E(5)

List / A / B / C / D / E
Ready
Start

2)Priority List: E(5), D(2), C(7) , B(5), A(6)

List
Ready
Start

3) Priority List:

A(6), E(5), C(7), D(2), B(5)

PRACTICE PROBLEMS: Find the Finishing Time and schedule for each project.

#1 Priority List: A(5), C(6), D(3), B(7), E(9), F(3)

#2 Priority List: F(3), A(5), E(6), B(8), D(4), C(2)


Section 8.4: Decreasing – Time Algorithm

Reminder: The priority list has ______to do with the precedence relations. It’s merely a preferred ordering of all tasks, but we still need a project digraph and processors to schedule.

Our goal is to try and find good priority lists to get the shortest possible processing time!!

STRATEGY #1:Do the longer jobs first and leave the shorter jobs for last.

  • Decreasing-Time Priority List:
  • If tasks have the same processing time (tie), then randomly order the tied tasks.

The process of scheduling using the decreasing-time priority list is called the Decreasing-Time Algorithm.

Example #1:

  1. Find the decreasing-time priority list for the project digraph.
  2. Use the Decreasing-Time Algorithm to find the schedule of your priority list for 2 processors.

Decreasing Time Priority List:

Example #2:Decreasing Time Priority List:

Example #3:Decreasing Time Priority List:

WEAKNESS:

HOMEWORK:p. 305 # 37 – 38

Section 8.5: Critical Paths

CRITICAL PATH for vertex/ task X: The _____ from X to END with the ______total processing time.

  • CRITICAL TIME for X: The ______processing time of _____ tasks on the critical path for X

CRITICAL PATH (for entire digraph): the path with the LONGEST processing time from START to END.

  • CRITICAL TIME: Total processing time of all tasks on the critical path for the START.

EXAMPLES: Find the critical path and time for several vertices.

  1. vertex HU
  1. vertex AD
  1. vertex IW
  1. Find the critical path.

OBSERVATIONS or PROBLEMS:

BACKFLOW ALGORITHM:finding critical paths efficiently

STEP 1: Find the critical time for every vertex of the project digraph.

  • Begin at END and working backward toward START according to the following rule:

Critical time = task’s processing time plus the largest critical time among the vertices incident from that task.

Always ADD THE LARGEST CRITICAL TIME BACKWARDS into the task processing time.

  • Randomly choose in case of ties as the time will still be the same

Notation:Square brackets [ ] = critical time Parentheses ( ) = processing time

Example of Step #1 for BACK FLOW ALGORITHM:

What is the critical time for vertex X?

STEP 2:CRITICAL PATH: Critical paths are found by following the LARGEST critical time of an adjacent TASK (vertex) to the end.

EXAMPLE 1:

  1. Find the critical time for each vertex in the given project digraph.
  2. Find the critical path and its for the given project digraph.

EXAMPLE 2:

  1. Find the critical time for each vertex in the given project digraph.
  2. Find the critical path and its time for the given project digraph.
  3. Find the critical path for task A:
  4. Find the critical path for task C:
  5. Find the critical path for task D:

EXAMPLE 3:

  1. Find the critical time for each vertex in the given project digraph.

FW =

PD =

EU =

IC =

HU =

PU =

PL =

IP =

ID =

IW =

IF =

AP =

AF =

AW =

AD =

  1. Find the critical path and it’s time for the given project digraph.
  1. Find critical path and time for IF:
  1. Find critical path and time for AW

Why are the critical paths and critical times significant?

CRITICAL PATH = a ______order that tasks must be completed in:

CRITICAL TIME = ______finishing time that the project can be completed in.

Section 8.6: Critical – Path Algorithm

We can now use the concept of critical paths to create very good although NOT always optimal schedules.

Creating schedules will require needing Critical-Time Priority List: the priority list of tasks written in decreasing order of CRITICAL TIMES with times broken randomly.

CRITICAL-PATH ALGORITHM:

STEP 1: Find Critical Times of each task

STEP 2: Create Critical-Time Priority List

STEP 3: Create Schedule using priority list and project digraph

EXAMPLE 1: Find the project time using Critical Path Algorithm with 2 processors for the given project digraph. (Critical Times were solved for in Section 8.5 examples)

PRIORITY LIST:

EXAMPLE 2:Use Critical Path Algorithm with 2 processors for the given project digraph.

PRIORITY LIST:

EXAMPLE 3: Find the project time using Critical Path Algorithm with 3 processors for the given project digraph. (Critical Times were solved for in Section 8.5 examples)

Critical Time Priority List:

AP, AF, AW, IF, IW, AD, IP, PL, HU, ID, IC, FW, PU, PD, EU

EXAMPLE 4: Use Critical Path Algorithm with 3 processors for the given project digraph.

Critical Time Priority List:

HOMEWORK: p.305 #45, 46, 48