ar/assignment1/3.tex

   1 \section{Problem 2}
   2 {\em
   3 Twelve jobs numbered from 1 to 12 have to be executed satisfying the following
   4 requirements:
   5 \begin{itemize}
   6         \item The running time of job $i$ is $i$, for $i=1,\ldots,12$
   7         \item All jobs run without interrupt.
   8         \item Job 3 may only start if jobs 1 and 2 have been finished.
   9         \item Job 5 may only start if jobs 3 and 4 have been finished.
  10         \item Job 7 may only start if jobs 3, 4 and 6 have been finished.
  11         \item Job 9 may only start if jobs 5 and 8 have been finished
  12         \item Job 11 may only start if job 10 has been finished.
  13         \item Job 12 may only start if jobs 9 and 11 have been finished.
  14         \item Jobs 5,7 en 10 require a special equipment of which only one copy
  15                 is available, so no two of these jobs may run at the same time.
  16 \end{itemize}
  17
  18 Find a solution of this scheduling problem for which the total running time is
  19 minimal.
  20 }
  21
  22 \newpage
  23 \subsection{Formal definition}
  24 For every job $j_{i}$ for $i\in J$ where $J=\{1,\ldots,12\}$ we define variable
  25 $j_{i}s$ for starting time. All jobs that have a shared resource we group as
  26 $J'=\{5,7,10\}$ and we define a function $p(i)$ that returns a set of all
  27 dependencies of job $i$. The total time it takes for all jobs to finish is $T$.
  28
  29 This leads to the following formalization where we minimize $T$.
  30 \begin{align}
  31         \bigwedge_{i\in J}\Biggl(
  32                 & j_{i}>0\wedge j_{i}+i<T\\
  33                 & \wedge \bigwedge_{k\in p(i)} j_{i}>j_{k}+k\Biggr)\\
  34                 & \wedge \bigwedge_{i\in J'}\bigwedge_{k\in J'}
  35                 i=j\vee j_{i}>j_{k}+k \vee j_{i}+i<j_{k}
  36 \end{align}
  37
  38 Every numbered subformula describes a group of constraints from the problem
  39 definition.
  40 \begin{itemize}
  41         \setcounter{enumi}{12}
  42         \item Makes sure that starting times are positive and that all jobs
  43                 finish before $T$.
  44         \item Makes sure that job may not start before all their dependencies
  45                 are finished by stating that they start strictly after their
  46                 dependency.
  47         \item Makes sure that never two more jobs use the shared resource by
  48                 stating that they either ends strictly before the other or
  49                 start strictly after the other.
  50 \end{itemize}
  51
  52 \subsection{SMT format solution}
  53 The formula is easily convertable via a script to SMT format by literal
  54 conversion and said script is listed in Listing~\ref{listing:a3.bash}. The
  55 script optimizes a little bit from the original formula by leaving out the
  56 shared resource checking for the same jobs. The minimization is done by
  57 incrementing variable $T$ every time the current $T$ yields unsat with a bash
  58 script shown in Listing~\ref{listing:3.bash}.
  59
  60 \lstinputlisting[language=bash,firstline=46,
  61         caption={Iteratively find the shortest solution for problem 3},
  62         label={listing:3.bash}]{src/a3.bash}
  63
  64 \subsection{Solution}
  65 The bash script finds and shows the minimal solution in which all jobs are
  66 finished in $37$ time units. Finding this solution takes less then $0.85$
  67 seconds and is shown in Figure~\ref{fig:s3}.
  68
  69 Light gray blocks represent normal tasks and the darker gray blocks represent
  70 tasks from $J'$.
  71
  72 \begin{figure}[H]
  73         \centering
  74         \includegraphics[width=\linewidth]{s3.png}
  75 \label{fig:s3}
  76         \caption{Solution visualization for problem 3}
  77 \end{figure}