\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial7}{Problems for Tutorial 7}{April 1, 1997}

\section {Task Scheduling with Finitely Many  Processors}

\noindent Consider a poset of W tasks where each task requires unit time to be completed.  Let D be the length of the longest (critical) path.  Show that if we have P processors then we can complete all the tasks in at most 
$D+\floor{\frac{W}{P}}$ time steps.  Show 
that this bound is within a factor of 2 of the optimal 
for that set of tasks run on an arbitrary number of processors.  \\ 

\section {Conflict Graphs}

\noindent 
Consider a collection of tasks $T_1,...,T_n$, where each $T_i$ has a set
of resource requirements $S_i$.  (Each $S_i$ is a subset of some
universal set of resources $R$.)
Each task needs exclusive access to its resources when it executes and
each task requires unit time to be executed.

(a) In terms of the $T_i$'s and the $S_i$'s, define a conflict graph
describing which tasks cannot execute at the same time. 

(b) If each task is supposed to execute once, describe in terms of your
conflict graph, a minimum-time schedule for all of them to execute. 
How long does it take for all the tasks to be executed? 


\end{document}
