Chapter 8 Mathematics of Scheduling



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

2. IN EXECUTION: processor has started and is ____________working on task

3. READY: ___________________ be started because _________ prerequisites have been completed

4. 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

2. UNIFORMITY: processing time for a task is the _________ regardless of the processor

3. PERSERVERANCE: processor will complete task _______________________________

• Notation: task X has a processing time of n units = X(n)

o 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

• NOTE: In every situation of scheduling, there is an absolute minimum time that the finishing time must be greater than or equal and it is based only on the precedence relations and processing times

Possible Schedules:

[pic]

Finishing Time =

[pic]

Finishing Time =

[pic]

Finishing Time =

[pic]

Finishing Time =

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:

o Direction = ____________ vertex to an _______ vertex

o XY:

o YX:

ARC-SET:

INCDENCE: relationship of vertices (direction of arcs)

o A incident to B

o To where are you going:

o E incident from D

From where are you going:

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”;

o OUTDEGREE OF VERTEX: # of arcs for which the vertex is the _______________ vertex

o 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 | |

|W |X ( W |

|X | |

|Y |Y ( V |

|Task |Precedence Relations |

|A | |

|B |B(C, B(F, B( G |

|C |C( A |

|D |D ( G |

|E |E (C |

|F |F (A, F( H |

|G |G(H |

|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.3: Scheduling with Priority Lists

Example #1: 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 NOT 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}

Means: If possible,

• OPTION #1: If task X is ready,

• OPTION #2: If task X is not ready (ineligible),

• OPTION #3: If task X and task Y are both not ready,

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 Processors Free: Assign ______________________ tasks in left to right priority to _________________________________________________processors

• Any unassigned processors must IDLE for new ready tasks

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.

REPEAT STEPS WHEN EACH NEW TASK IS COMPLETED!!!!

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

1) 2 Processors: P1 and P2 and

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

[pic]

2) 2 Processors: P1 and P2

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

[pic]

3) 2 Processors: P1, P2

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

[pic]

PRACTICE PROBLEMS:

For two processors and the project digraph, find the Finishing Time and schedule for each project.

#1 Priority List: A(5), C(6), D(4), 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:

a. Find the decreasing-time priority list for the project digraph.

b. 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.

[pic]

1. vertex HU

2. vertex AD

3. vertex IW

4. 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

o Example of Step #1 for BACK FLOW ALGORITHM:

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

EXAMPLE 1:

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

b. Find the critical path and its for the given project digraph.

[pic]

EXAMPLE 2:

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

b. Find the critical path and its time for the given project digraph.

c. Find the critical path for task A:

d. Find the critical path for task C:

e. Find the critical path for task D:

[pic]

EXAMPLE 3:

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

b. Find the critical path and it’s time for the given project digraph.

c. Find critical path and time for IF:

d. Find Critical path and time for AW

[pic]

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)

[pic]

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

[pic]

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)

[pic]

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.

[pic]Critical Time Priority List: HOMEWORK: p.305 #45, 46, 48

Section 8.7: Scheduling with Independent Tasks

What are INDEPENDENT TASKS?

What does the project digraph of independent tasks look like?

Draw the project digraph for independent tasks A(5), B(2), C(3), D(7)

What is the critical time for every vertex when all tasks are independent?

EXAMPLE 1: 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).

1a. Find the schedule for each of the following priority lists:

Priority List #1: A(70), B(90), C(100), D(70), E(80), F(20), G(20), H(80), I(10).

Decreasing/ Critical Time Priority List

C(100), B(90), E(80), H(80), A(70), D(70), F(20), G(20), I(10).

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

How do independent tasks affect scheduling?

1) All tasks are automatically _________________________ from the start

2) Since all tasks are ready, then processors will __________________________ until there are _________ remaining tasks to work on

3) We can use times only to get shortest possible schedule without a priority list

Example 2: 3 Processors and tasks with processing times given in minutes

A(50), B(30), C(40), D(30), E(50), F(30), G(40)

a) What do you think is the optimal time, why?

b) Try to create the optimal schedule?

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

a) What do you think is the optimal time, why?

b) Try to create the optimal schedule?

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

a) What do you think is the optimal time, why?

b) Try to create the optimal schedule?

Practice on your own:

1) 18 INDEPENDENT tasks with processing times (in hours) given by 1, 2, 3, …, 17 ,18.

a. Find the finishing time Fin for N = 3 processors using the critical-path algorithm.

b. Find the optimal finishing time Opt for the processors.

2) 11 INDEPENDENT tasks with processing times (in hours) given by

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and 89

a. Find the finishing time Fin for N = 2 processors using the critical-path algorithm.

3) 12 INDEPENDENT tasks with processing times (in hours) given by

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and 144

a. Find the finishing time Fin for N = 2 processors using the decreasing-time algorithm.

HOMEWORK: p.306 #51 - 53, 55 (Find optimal schedule and time only for given tasks)

-----------------------

Y

Z

Y

Y

X

X

Y

W

X

X

Z

2

0

4

6

8

12

10

14

P1:

P2:

2

0

4

6

8

12

10

14

P1:

P2:

2

0

4

6

8

12

10

14

P1:

P2:

2

0

4

6

8

12

10

14

P1:

P2:

B

B

B

B

G

G

G

G

A

B

C

D

E

Y

Y

X

X

A

E

C

D

B

START(0)

A(6)

B(5)

C (7)

END(0)

D(2)

E(5)

START(0)

A(6)

B(5)

C (7)

END(0)

D(2)

E(5)

2

0

4

6

8

12

10

14

16

18

20

Time:

P1:

P2:

START(0)

A(6)

B(5)

C (7)

END(0)

D(2)

E(5)

2

0

4

6

8

12

10

14

16

18

20

Time:

P1:

P2:

2

0

4

6

8

12

10

14

16

18

20

Time:

P1:

P2:

START(0)

C(6)

B(7)

A(5)

F(3)

D(3)

E(9)

END(0)

2

0

4

6

8

12

10

14

16

18

20

Time:

P1:

P2:

START(0)

C(2)

B(8)

A(5)

F(3)

D(4)

E(6)

END(0)

2

0

4

6

8

12

10

14

16

18

20

Time:

P1:

P2:

2

0

4

6

8

12

10

14

P1:

P2:

START(0)

A(6)

B(5)

C (7)

END(0)

D(2)

E(5)

START(0)

C(6)

B(7)

A(5)

F(3)

D(3)

E(9)

END(0)

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

START(0)

C(2)

B(8)

A(5)

F(3)

D(4)

E(6)

END(0)

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

X(p)

A[10]

B[15]

C[12]

START(0)

C(5)

B(2)

A(1)

END(0)

D(4)

E(7)

F(6)

G(3)

H(2)

START(0)

A(6)

B(5)

C (7)

END(0)

D(2)

E(5)

START(0)

C(5) [11]

B(1) [12]

A(1) [10]

END(0)

D(4) [7]

E(7) [9]

F(6) [6]

G(3) [3]

H(2) [2]

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

START(0)

C(3)

B(2)

A(8)

END(0)

D(6)

E(7)

F(5)

G(4)

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

P3:

22

24

26

28

30

32

34

END(0)

START(0)

A(7)

B(5)

C(6)

*`ghjœìí

2 3 d e f p q r s w x y z { ’ “ ïåÞ×ÞåÏÞÄÞϼϭ¡•¡ˆxmie]RiÏKiÏ

hXê5?\?h…7Kh…7K5?\?]?hJDühXê5?h…7KhXêhXê5?6?>*[pic]\?]?hÉI¦hXê5?6?>*[pic]CJ\?]?hXê5?6?>*[pic]CJ\?]?h›&BhXêCJ\?]?h›&BhXêCJ \?]?h›&BhXê5?>*[pic]CJ \?]?h…7K5?\?]?hJDühXê>*[pic]\?]?hXê5?D(5)

E(3)

F(4)

G(4)

H(2)

I(5)

J(3)

2

0

4

6

8

12

10

14

16

18

20

P1:

P2:

P3:

22

24

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download