Difference between revisions of "Walther MA279 Spring2016 topic10" - Rhea

Revision as of 13:43, 21 April 2016

The Mathematics of Scheduling

Scheduling is arranging or planning events to occur at a certain time. It serves as an answer to questions such as "How long does it take to build a house?" The answer to this simple question is actually quite complicated due to the many factors that must be considered. For instance, there are obvious factors, such as the size of the house, or the materials needed; however, there are more complicated factors, like coordinating people and equipment to accomplish the goal in a timely way. This leads to the study of Combinatorial Scheduling.

Basic Definitions

•Processors- These are the "workers" that will complete the tasks

•Tasks - This is an indivisible unit of work

•Processing Time - The time needed for a processor to complete a given task, X

Basic Assumptions

For simplicity, we assume the following three assumptions

•Versatility - Any processor can execute an task

•Uniformity - The processing time for a task is the same regardless of which processor is executing the task

•Perseverance - Once a processor starts a task, it will complete the task without interruption

Precedence Relations

If you cannot complete a task Y, without first completing a task X, (X→Y) this is referred to as a Precedence Relation

However, two tasks are said to be Independent if neither X nor Y have a precedence relation.

Another note about precedence relations is that they exhibit transitivity. If (X→Y) and (Y→Z), then (X→Z).

Lastly, we cannot have a set of precedence relations that form a cycle. In other words, we cannot have (X→Y) and (Y→Z) and (Z→X).

More Terminology

•Project-A set of tasks to be completed

•Finishing Time - The duration of the project from the start of the first task to the completion of the last task

•Optimal Schedule- A schedule with the minimum project finishing time or has the optimal finishing time

A note about the optimal finishing time is that the optimal finishing time for any project is the minimum sum of time of the precedence relationships. For example, given tasks W, X, Y, and Z and an infinite number of processors, and if Y cannot be completed before X, but W, X, and Z are independent, then the minimum finishing time is the combined time of X and Y.

•Directed Graphs (Digraphs)

Digraphs serve as a way to represent asymmetric relationships (i.e. X related to Y does not imply Y is related to X)

The following terminology apply to digraphs:

•Arcs- Similar to edges, every arc is described by its starting vertex and ending vertex. Thus XY describes X→Y, but does not apply to Y→X

•Arc-set- This is a list of all arcs in a digraph. For example digraph A = {XY, YX}

•Incident to/from- If XY is an arc in the digraph, X is incident to Y, similarly Y is incident from X

•Adjacent- If the starting point of YZ is the ending point of XY, then YZ is adjacent. In other words, one can go from X to Z by way of Y

•Path- The sequence of arcs from one vertex to another. For example a path from vertex X to vertex W could consist of a sequence of arcs XY,YZ,ZU...., VW.

•Cycle- When a path starts and ends on the same vertex

•Outdegree/Indegree- The outdegree of vertex X is the number of arcs with X as their starting point, likewise the indexer of vertex X is the number of arcs with X as their ending point.

Below are examples of digraphs:

Priority Lists

A list of all the tasks prioritized in the order we prefer to execute them is a priority list.

The number of priority lists in a project consisting of M tasks is M! = M X (M-1) X .... X 2 X 1

Scheduling Algorithms

Decreasing-Time Algorithm - This algorithm creates a priority list based on decreasing time. For example, given WX(8), XY(2), and YZ(4) (where the time for each task is given by the numbers in the parenthesis), then the decreasing-time priority list is WX,YZ,XY. The problem with this algorithm is that it is "greedy." In other words, it does not account for precedence relationships, and only prioritizes things in the movement of decisions.

Critical Paths and Times

•For a given vertex X of a project digraph, the critical path for X is the path from X to END with the longest processing time (the sum of all processing times along this path). When we add the processing times of all the tasks along the critical path for a vertex X, we get a Critical time for X

•The path with the longest processing time from START to END is called the critical path for the project, and the total processing time for this critical path is called the critical time for the project.

Backflow Algorithm- The backflow algorithm is used to find as;dklfj;laksdjf;lkasdjfl;dasd;lfkjas;kdf Critical Paths Algorithm- If there is a long set of tasks that need to be completed in order, then this algorithm accounts for this, and places higher priority on tasks that precede a larger set of tasks. The algorithm is as follows:

Step 1: Use