\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 {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? 

\section {Conflict Graphs and Precedence}

\noindent  Consider again a set of tasks $T_1, \dots, T_n$, where each has a
set of resource requirements $S_i$.
As before, each task needs exclusive access to its resources, and each
task requires unit time, but in addition, there is a precedence relation between the tasks -- some tasks are required to precede other tasks.

Develop a good method for scheduling all the tasks, each exactly
once.  Try to minimize the total schedule time.


\end{document}
