Scheduling   157 
Optimal Schedule 
An optimal schedule is the schedule with the shortest possible finishing time. 
For two processors, things become more interesting.  For small digraphs like this, we 
probably could fiddle around and guess-and-check a pretty good schedule.  Here would be a 
possibility: 
Time:  0    1    2    3    4    5    6    7    8    9    10 
7    8    9    10 
10 
P
1
T
T
3
T
6
T
9
P
T
T
T
2
T
8
T
7
With two processors, the finishing time was reduced to 5.5 days.  What was processor 2 
doing during the last day?  Nothing, because there were no tasks for the processor to do.  
This is called idle time.   
Idle Time 
Idle time is time in the schedule when there are no tasks available for the processor to 
work on, so they sit idle. 
Is this schedule optimal?  Could it have been completed in 5 days?  Because every other task 
had to be completed before task 9 could start, there would be no way that both processors 
could be busy during task 9, so it is not possible to create a shorter schedule. 
So how long will it take if we use three processors?  About 10/3 = 3.33 days?  Again we will 
guess-and-check a schedule: 
Time:  0    1    2    3    4    5    6    7    8    9    10 
7    8    9    10 
10 
P
1
T
T
2
T
6
T
8
T
9
P
T
T
7
P
3
T
4
T
5
With three processors, the job still took 4.5 days.  It is a little harder to tell whether this 
schedule is optimal.  However, it might be helpful to notice that since Task 1, 2, 6, and 9 
have to be completed sequentially, there is no way that this job could be completed in less 
than 2+0.5+0.5+1 = 4 days, regardless of the number of processors.  Four days is, for this 
digraph, the absolute minimum time to complete the job, called the critical time. 
Critical Time 
The critical time is the absolute minimum time to complete the job, regardless of the 
number of processors working on the tasks. 
Critical time can be determined by looking at the longest sequence of tasks in the 
digraph, called the critical path 
Pdf security settings - C# PDF Digital Signature Library: add, remove, update PDF digital signatures in C#.net, ASP.NET, MVC, WPF
Help to Improve the Security of Your PDF File by Adding Digital Signatures
change pdf security settings; decrypt password protected pdf
Pdf security settings - VB.NET PDF Digital Signature Library: add, remove, update PDF digital signatures in vb.net, ASP.NET, MVC, WPF
Guide VB.NET Programmers to Improve the Security of Your PDF File by Adding Digital Signatures
convert locked pdf to word; decrypt a pdf
158 
Adding an algorithm 
Up until now, we have been creating schedules by guess-and-check, which works well 
enough for small schedules, but would not work well with dozens or hundreds of tasks.  To 
create a more procedural approach, we might begin by somehow creating a priority list.  
Once we have a priority list, we can begin scheduling using that list and the list processing 
algorithm. 
Priority List 
A priority list is a list of tasks given in the order in which we desire them to be 
completed. 
The List Processing Algorithm turns a priority list into a schedule 
List Processing Algorithm 
1.  On the digraph or priority list, circle all tasks that are ready, meaning that all pre-
requisite tasks have been completed. 
2.  Assign to each available processor, in order, the first ready task.  Mark the task as 
in progress, perhaps by putting a single line through the task. 
3.  Move forward in time until a task is completed.  Mark the task as completed, 
perhaps by crossing out the task.  If any new tasks become ready, mark them as 
such.  
4.  Repeat until all tasks have been scheduled. 
Example 2 
Using our digraph from above, schedule it using the priority list below: 
T
1
, T
3
, T
4
, T
5
, T
6
, T
7
, T
8
, T
2
, T
9
Time 0:  Mark ready tasks 
Priority list:  T
1
,   T
3
,   T
4
,   T
5
,   T
6
,   T
7
,   T
8
,   T
2
,   T
9
We assign the first task, T
1
to the first processor, P
1
, and the second ready task, T
3
, to the 
second processor.   Making those assignments, we mark those tasks as in progress: 
Priority list:  T
1
,   T
3
,   T
4
,   T
5
,   T
6
,   T
7
,   T
8
,   T
2
,   T
9
Schedule up to here: 
We jump to the time when the next task completes, which is at time 2. 
Time:  0    1    2    3    4    5    6    7    8    9    10 
7    8    9    10 
10 
P
1
T
P
T
VB.NET PDF Password Library: add, remove, edit PDF file password
RasterEdge XDoc.PDF SDK provides some PDF security settings about password to help protect your PDF document in VB.NET project.
decrypt pdf with password; decrypt pdf file online
C# PDF Password Library: add, remove, edit PDF file password in C#
Able to change password on adobe PDF document in C#.NET. To help protect your PDF document in C# project, XDoc.PDF provides some PDF security settings.
change security settings on pdf; create pdf the security level is set to high
Time:  0    1    2    3    4    5    6    7    8    9    10 
7    8    9    10 
10 
P
1
T
T
4
T
2
T
6
T
7
P
T
T
T
8
Online Change your PDF file Permission Settings
easy as possible to change your PDF file permission settings. You can receive the locked PDF by simply clicking download and you are good to go!. Web Security.
pdf secure signature; pdf security settings
Online Split PDF file. Best free online split PDF tool.
You can use our .NET PDF SDK to set file split settings for your PDF You can receive the PDF files by simply clicking download and you are good to Web Security.
pdf encryption; create pdf security
tasks in order from longest completion time to 
Time:  0    1    2    3    4    5    6    7    8    9    10 
7    8    9    10 
10 
P
1
T
T
4
T
2
T
6
T
7
T
9
P
T
T
T
8
Online Remove password from protected PDF file
If we need a password from you, it will not be read or stored. To hlep protect your PDF document in C# project, XDoc.PDF provides some PDF security settings.
change pdf security settings reader; create secure pdf online
VB.NET PDF Library SDK to view, edit, convert, process PDF file
PDF Document Protection. XDoc.PDF SDK allows users to perform PDF document security settings in VB.NET program. Password, digital
convert locked pdf to word doc; copy text from encrypted pdf
ority list by listing the 
T
1
(6) 
T
5
(5) 
T
2
(3) 
T
3
(7) 
T
4
(4) 
T
6
(10) 
T
7
(4) 
T
10
(7) 
T
8
(3) 
T
9
(2) 
T
P
1
P
2
T
T
P
1
P
2
T
T
10 
T
P
1
P
2
T
T
10 
T
C# HTML5 Viewer: Deployment on AzureCloudService
RasterEdge.XDoc.PDF.HTML5Editor.dll. system.webServer> <validation validateIntegratedModeConfiguration="false"/> <security> <requestFiltering
decrypt pdf password online; change security settings pdf
C# HTML5 Viewer: Deployment on ASP.NET MVC
RasterEdge.XDoc.PDF.HTML5Editor.dll. system.webServer> <validation validateIntegratedModeConfiguration="false"/> <security> <requestFiltering
copy from locked pdf; creating a secure pdf document
162 
Time 10:  Both processors complete their tasks.  T
6
becomes ready, and is assigned to P
1
.  
No other tasks are ready, so P
2
idles. 
Priority list: T
6, 
T
3
,   T
10
,   T
1
,   T
5
,   T
4
,   T
7
,   T
2
  T
8
,   T
Time 20:  With T
6
complete, T
5
and T
7
become ready, and are assigned to P
1
and P
2
respectively. 
Priority list: T
6, 
T
3
,   T
10
,   T
1
,   T
5
,   T
4
,   T
7
,   T
2
  T
8
,   T
Time 24:  P
2
completes T
7
.  No new items become ready, so P
2
idles. 
Time 25:  P
1
completes T
5
.  T
8
and T
9
become ready, and are assigned. 
Priority list: T
6, 
T
3
,   T
10
,   T
1
,   T
5
,   T
4
,   T
7
,   T
2
  T
8
,   T
Time 27:  T
9
is completed.  No items ready, so P
2
idles. 
Time 28:  T
8
is completed.  T
10
becomes ready, and is assigned to P
1
Priority list: T
6, 
T
3
,   T
10
,   T
1
,   T
5
,   T
4
,   T
7
,   T
2
  T
8
,   T
This is our completed schedule, with a finishing time of 35. 
T
P
1
P
2
T
T
10 
T
T
20 
T
P
1
P
2
T
T
10 
T
T
20 
T
T
25 
24 
T
P
1
P
2
T
T
10 
T
T
20 
T
T
25 
24 
T
T
28 
27 
T
P
1
P
2
T
T
10 
T
T
20 
T
T
25 
24 
T
T
28 
27 
T
10 
35 
Online Convert Jpeg to PDF file. Best free online export Jpg image
the conversion settings you like, and download it with one click. The entire process is quick, free and very easy. Web Security. All your JPG and PDF files will
convert locked pdf to word online; cannot print pdf security
Scheduling   163 
Using the decreasing time algorithm, the priority list led to a schedule with a finishing time 
of 35.  Is this good?  It certainly looks like there was a lot of idle time in this schedule.  To 
get some idea how good or bad this schedule is, we could compute the critical time, the 
minimum time to complete the job.  To find this, we look for the sequence of tasks with the 
highest total completion time.  For this digraph that sequence would appear to be:  T
2
, T
6
, T
5
T
8
, T
10
, with total sequence time of 28.  From this we can conclude that our schedule isn’t 
horrible, but there is a possibility that a better schedule exists.   
Try it Now 2 
Determine the priority list for the digraph from Try it Now 1 using the decreasing time 
algorithm. 
Critical path algorithm 
A sequence of tasks in the digraph is called a path.  In the previous example, we saw that the 
critical path dictates the minimum completion time for a schedule.  Perhaps, then, it would 
make sense to consider the critical path when creating our schedule.  For example, in the last 
schedule, the processors began working on tasks 1 and 3 because they were longer tasks, but 
starting on task 2 earlier would have allowed work to begin on the long task 6 earlier. 
The critical path algorithm allows you to create a priority list based on idea of critical paths.   
Critical Path Algorithm (version 1) 
1.  Find the critical path.  
2.  The first task in the critical path gets added to the priority list. 
3.  Remove that task from the digraph 
4.  Repeat, finding the new critical path with the revised digraph. 
Example 4  
The original digraph from Example 3 has critical path T
2
, T
6
, T
5
, T
8
, T
10
, so T
2
gets added 
first to the priority list.  Removing T
2
from the digraph, it now looks like: 
The critical path (longest path) in the remaining digraph is now T
6
, T
5
, T
8
, T
10
, so T
6
is added 
to the priority list and removed. 
T
1
(6) 
T
5
(5) 
T
3
(7) 
T
4
(4) 
T
6
(10) 
T
7
(4) 
T
10
(7) 
T
8
(3) 
T
9
(2) 
164 
Now there are two paths with the same longest length: T
1
, T
5
, T
8
, T
10
and T
3
, T
7
, T
8
, T
10
.  We 
can add T
1
to the priority list (or T
3
– we usually add the one with smaller item number) and 
remove it, and continue the process. 
I’m sure you can imagine that searching for the critical path every time you remove a task 
from the digraph would get really tiring, especially for a large digraph.  In practice, the 
critical path algorithm is implementing by first working from the end backwards.  This is 
called the backflow algorithm. 
Backflow Algorithm 
1.  Introduce an “end” vertex, and assign it a time of 0, shown in [brackets] 
2.  Move backwards to every vertex that has an arrow to the end and assign it a critical 
time 
3.  From each of those vertices, move backwards and assign those vertices critical 
times.  Notice that the critical time for the earlier vertex will be that task’s time plus 
the critical time for the later vertex.   
Example:  Consider this segment of digraph. 
In this case, if T2 has already been determined to have a critical time of 10, then T1 
will have a critical time of 5+10 = 15 
If you have already assigned a critical time to a vertex, replace it only if the new 
time is larger.   
Example:  In the digraph below, T1 should be labeled with a critical time of 16, 
since it is the longer of 5+10 and 5+11. 
4.  Repeat until all vertices are labeled with their critical times 
T
1
(6) 
T
5
(5) 
T
3
(7) 
T
4
(4) 
T
7
(4) 
T
10
(7) 
T
8
(3) 
T
9
(2) 
T
1
(5) 
T
2
(4) [10] 
T
1
(5) [15] 
T
2
(4) [10] 
T
1
(5) 
T
2
(4) [10] 
T
3
(5) [11] 
] 
Scheduling   165 
One you have completed the backflow algorithm, you can easily create the critical path 
priority list by using the critical times you just found. 
Critical Path Algorithm (version 2) 
1.  Apply the backflow algorithm to the digraph  
2.  Create the priority list by listing the tasks in order from longest critical time to 
shortest critical time 
This version of the Critical Path Algorithm will usually be the easier to implement. 
Example 5 
Applying this to our digraph from the earlier example, we start applying the backflow 
algorithm.   
We add an end vertex and give it a critical time of 0. 
We then move back to T
4
, T
9
, and T
10
, labeling them with their critical times 
From each vertex marked with a critical time, we go back.  T
7
, for example, will get labeled 
with a critical time 11 – the task time of 4 plus the critical time of 7 for T
10
.  For T
5
, there are 
two paths to the end.  We use the longer, labeling T
5
with critical time 5+7 = 12.  
T
1
(6) 
T
5
(5) 
T
2
(3) 
T
3
(7) 
T
4
(4) 
T
6
(10) 
T
7
(4) 
T
10
(7) 
T
8
(3) 
T
9
(2) 
End [0] 
T
1
(6) 
T
5
(5) 
T
2
(3) 
T
3
(7) 
T
4
(4) [4] 
T
6
(10) 
T
7
(4) 
T
10
(7) [7] 
T
8
(3) 
T
9
(2) [2] 
End [0] 
166 
Continue the process until all vertices are labeled.  Notice that the critical time for T
5
ended 
got replaced later with the even longer path through T
8
We can now quickly create the critical path priority list by listing the tasks in decreasing 
order of critical time: 
Priority list: T
2
, T
6
, T
1
, T
3
, T
5
, T
7
, T
8
, T
10
, T
4
, T
9
Applying this priority list using the list processing algorithm, we get the schedule: 
In this particular case, we were able to achieve the minimum possible completion time with 
this schedule, suggesting that this schedule is optimal.  This is certainly not always the case. 
Try it Now 3 
Determine the priority list for the digraph from Try it Now 1 using the critical path 
algorithm. 
T
1
(6) 
T
5
(5) [12] 
T
2
(3) 
T
3
(7) 
T
4
(4) [4] 
T
6
(10) 
T
7
(4) [14] 
] 
T
10
(7) [7] 
T
8
(3) [10] 
T
9
(2) [2] 
End [0] 
T
1
(6) [21] 
T
5
(5) [15] 
] 
T
2
(3) [28] 
] 
T
3
(7) [21] 
] 
T
4
(4) [4] 
T
6
(10) [25] 
] 
T
7
(4) [14] 
] 
T
10
(7) [7] 
T
8
(3) [10] 
T
9
(2) [2] 
End [0] 
T
P
1
P
2
T
T
17 
T
T
13 
T
T
18 
23 
T
T
21 
T
28 
Documents you may be interested
Documents you may be interested