From c488bc4970823dfc740d5473d6fa928edc58242e Mon Sep 17 00:00:00 2001 From: Yigit Sever Date: Tue, 1 Dec 2020 23:08:08 +0300 Subject: Include the answer to first question --- answer_sheet/main.pdf | Bin 0 -> 141549 bytes answer_sheet/main.tex | 50 +++++++++++++++++++++++++++++++++++++++++++++ answer_sheet/q1_1.dia | Bin 0 -> 1604 bytes answer_sheet/q1_1.png | Bin 0 -> 6095 bytes answer_sheet/q1_2.png | Bin 0 -> 5486 bytes answer_sheet/q1_3.png | Bin 0 -> 5131 bytes answer_sheet/structure.tex | 1 + 7 files changed, 51 insertions(+) create mode 100644 answer_sheet/main.pdf create mode 100644 answer_sheet/q1_1.dia create mode 100644 answer_sheet/q1_1.png create mode 100644 answer_sheet/q1_2.png create mode 100644 answer_sheet/q1_3.png diff --git a/answer_sheet/main.pdf b/answer_sheet/main.pdf new file mode 100644 index 0000000..26316cd Binary files /dev/null and b/answer_sheet/main.pdf differ diff --git a/answer_sheet/main.tex b/answer_sheet/main.tex index 2d423e5..f9cd5d4 100644 --- a/answer_sheet/main.tex +++ b/answer_sheet/main.tex @@ -11,4 +11,54 @@ \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} diff --git a/answer_sheet/q1_1.dia b/answer_sheet/q1_1.dia new file mode 100644 index 0000000..8581469 Binary files /dev/null and b/answer_sheet/q1_1.dia differ diff --git a/answer_sheet/q1_1.png b/answer_sheet/q1_1.png new file mode 100644 index 0000000..113a872 Binary files /dev/null and b/answer_sheet/q1_1.png differ diff --git a/answer_sheet/q1_2.png b/answer_sheet/q1_2.png new file mode 100644 index 0000000..6e420d0 Binary files /dev/null and b/answer_sheet/q1_2.png differ diff --git a/answer_sheet/q1_3.png b/answer_sheet/q1_3.png new file mode 100644 index 0000000..a07fffa Binary files /dev/null and b/answer_sheet/q1_3.png differ diff --git a/answer_sheet/structure.tex b/answer_sheet/structure.tex index 9b7b1f9..77d3e4c 100644 --- a/answer_sheet/structure.tex +++ b/answer_sheet/structure.tex @@ -33,6 +33,7 @@ \usepackage[super]{nth} \usepackage{caption} \usepackage{tikz} +\usepackage{subcaption} \usetikzlibrary{arrows,fit,positioning} \usepackage[style=authoryear]{biblatex} -- cgit v1.2.3-70-g09d2