1 files changed, 50 insertions, 0 deletions

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}