blob: f9cd5d4b139b1a4f51f8e958901f732527139572 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
\documentclass{article}
\input{structure.tex}
\title{CENG567: Homework \#3}
\author{Yiğit Sever}
\date{\today}
\addbibresource{mylib.bib}
\begin{document}
\maketitle
\section{Job Scheduling}%
\label{sec:job_scheduling}
First we will state the variables we will use.
A job $n_i \in n$ is split into preprocessing $p_i \in p$ and indexing $f_i \in f$ per the question text.
With the given question text, we will ignore any kind of utilisation or efficiency concerns.
In other words, we will not care about the number of PCs we employ nor the time they will stay idle.
So, every indexing job $f_i \in f$ will be run on a separate PC\@.
Since we cannot pipeline the preprocessing jobs $p_{i} \in p$, any kind of real choice we have will be done on the $f_i \in f$.
The trivial case is when the preprocessing jobs are the \enquote{bottleneck} of the system, where;
\begin{equation*}
\forall p_{i} \in p > \forall f_{i} \in f
\end{equation*}
The completion time in this case is minimized by sorting the $f_{i} \in f$ and placing the \emph{shortest} $f_{i}$ last.
\begin{figure}[htpb]
\centering
\includegraphics[width=0.5\linewidth]{q1_1}
\caption{The trivial case where preprocessing jobs are all longer than the indexing jobs}%
\label{fig:q1_1}
\end{figure}
This approach extends to the case where the preprocessing time can be shorter than the indexing time as well.
In the example given in Figure~\ref{fig:1_cases}, two preprocessing jobs $p_1$ and $p_2$ both take 1 unit of time.
Whereas, the indexing jobs tied to the preprocessing jobs $f_1$ and $f_2$ take 5 and 1 units of time, respectively.
By scheduling the preprocessing task that is tied to the longest indexing job $p_1$ first, we can finish the whole computation in 6 time units which takes 7 time units in the other case.
Formally, the algorithm we propose simply sorts the $f_i \in f$ in $\mathcal{O}(n\log(n))$ time and schedules the jobs with respect to $f_i \in f$ (so the $p_i \in p$ tied to $f_i \in f$) from longest to shortest.
\begin{figure}
\centering
\begin{subfigure}[b]{0.45\textwidth}
\includegraphics[width=\textwidth]{q1_2}
\caption{The longest task is scheduled first}%
\label{subfig:1_1}
\end{subfigure}
~
\begin{subfigure}[b]{0.45\textwidth}
\includegraphics[width=\textwidth]{q1_3}
\caption{The longest task is scheduled last}%
\label{subfig:1_2}
\end{subfigure}
\caption{The worked example of the cases}%
\label{fig:1_cases}
\end{figure}
\end{document}
|
