7.3: Adding an algorithm

Last updated
Save as PDF

Page ID: 34213

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\ket}[1]{\left| #1 \right>}$
$\newcommand{\bra}[1]{\left< #1 \right|}$
$\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}$
$\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}$
$\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}$
$\newcommand{\op}[1]{\hat{\mathbf{#1}}}$
$\newcommand{\expect}[1]{\langle #1 \rangle}$
$\newcommand{\dfn}[1]{\emph{\textbf{#1}}}$

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

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

On the digraph or priority list, circle all tasks that are ready, meaning that all pre-requisite tasks have been completed.
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.
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.
Repeat until all tasks have been scheduled.

Example 2

Using our digraph from above, schedule it using the priority list below:

$\mathrm{T}_{1}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Solution

Time 0: Mark ready tasks

Priority list: $({\mathrm{T}_{1}}), (\mathrm{T}_{3}), (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

We assign the first task, $\mathrm{T}_{1}$ to the first processor, $\mathrm{P}_{1}$, and the second ready task, $\mathrm{T}_{3}$, to the second processor. Making those assignments, we mark those tasks as in progress:

Priority list: $\cancel{(\mathrm{T}_{1})}, \cancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Schedule up to here:

$clipboard_e77fb190a3f596755cb0ed99767471a80.png$

We jump to the time when the next task completes, which is at time 2.

Time 2: Both processors complete their tasks. We mark those tasks as complete. With Task 1 complete, Task 2 becomes ready:

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

We assign the next ready task on the list, $\mathrm{T}_{4}$ to $\mathrm{P}_{1}$, and $\mathrm{T}_{5}$ to $\mathrm{P}_{2}$.

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \cancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

$clipboard_ed931c39742cb3d6bfcc67592f093b557.png$

Time 3: Processor 1 has completed $\mathrm{T}_{4}$. Completing $\mathrm{T}_{4}$ does not make any other tasks ready (note that all the rest require that $\mathrm{T}_{2}$ be completed first).

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

Since the next three tasks are not yet ready, we assign the next ready task, $\mathrm{T}_{2}$ to $\mathrm{P}_{1}$

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \cancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5f8d7915ae037b71ff7e5fa3c51f66de.png$

Time 3.5: Processor 1 has completed $\mathrm{T}_{2}$. Completing $\mathrm{T}_{2}$ causes $\mathrm{T}_{6}$ and $\mathrm{T}_{7}$ to become ready. We assign $\mathrm{T}_{6}$ to $\mathrm{P}_{1}$.

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \cancel{(\mathrm{T}_{6})}, (\mathrm{T}_{7}), \mathrm{T}_{8}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5d65817f8fa5dc929322c44dbfb1f85a.png$

Time 4: Both processors complete their tasks. The completion of $\mathrm{T}_{5}$ allows $\mathrm{T}_{8}$ to become ready. We assign $\mathrm{T}_{7}$ to $\mathrm{P}_{1}$ and $\mathrm{T}_{8}$ to $\mathrm{P}_{2}$.

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \cancel{(\mathrm{T}_{7})}, \cancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e00d40539291882f1466b3b9ba4fc17fc.png$

Time 4.5: Both processors complete their tasks. $\mathrm{T}_{9}$ becomes ready, and is assigned to $\mathrm{P}_{1}$. There is no ready task for $\mathrm{P}_{2}$ to work on, so $\mathrm{P}_{2}$ idles.

Priority list: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \xcancel{(\mathrm{T}_{7})}, \xcancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \cancel{(\mathrm{T}_{9})}$

$clipboard_e7bc0f4b15e2eb217727706f983d188af.png$

With the last task completed, we have a completed schedule, with finishing time 5.5 days.

Try it Now 1

Using the digraph below, create a schedule using the priority list:

$\mathrm{T}_{1}, \mathrm{T}_{2}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{9}$

$sc3.svg$

Answer

Time 0: Tasks 1, 4, and 7 are ready. Assign Tasks 1 and 4

Time 9: Task 4 completes. Only task 7 is ready; assign task 7

Time 10: Task 1 completes. Task 2 now ready. Assign task 2

Time 17: Task 2 completes. Nothing is ready. Processor 1 idles

Time 22: Task 7 completes. Tasks 5 and 8 are ready. Assign tasks 5 and 8

Time 26: Task 8 completes. Task 9 is ready. Assign task 9

Time 27: Task 5 completes. Tasks 3 and 6 are ready. Assign task 3

Time 31: Task 3 completes. Assign task 6

Time 35: Everything is done. Finishing time is 35 for this schedule.

$clipboard_eeee2de77e15748630b6197c99fed34fc.png$

It is important to note that the list processing algorithm itself does not influence the resulting schedule – the schedule is completely determined by the priority list followed. The list processing, while do-able by hand, could just as easily be executed by a computer. The interesting part of scheduling, then, is how to choose a priority list that will create the best possible schedule.

Search

Text Color

Text Size

Margin Size

Font Type

Solution