
\section{Parallel Scheduling}

Assembling a car involves many small \term{tasks}.  And there are
constraints on the order of these tasks; for example, seats should
probably be installed before the doors are attached.  If there are
enough \term{processors} available (human workers or robots), then
work on some tasks can proceed in parallel; for example, some
processors can build the engine while others prepare the body of the
car.  Given a partially-ordered set of tasks and a supply of
processors, how should the work be scheduled to complete the assembly
as quickly as possible?

Computer scientists spend enormous effort studying scheduling problems
like this one because so many important practical problems can be cast
in these terms.  As an introduction, we're going to look at a
relatively simple scheduing problem.  In our problem, there is an
unlimited number of processors availabe, there is a poset of tasks to
be completed, and each processor can complete each task in 1 unit of
time.  The goal is to complete all the tasks as quickly as possible.

As a concrete example, let's return to the problem of getting dressed.
Suppose that you now have an unlimited number of robotic assistants
helping you.  Each robot can add one garment in one minute, subject to
the ordering constraints.  How should the work be scheduled?  Here is
one possibility:

\mfigure{!}{2in}{getting-dressed2}

All tasks are completed in four minutes using this schedule.  And
there is no hope of doing better, because there is a sequence of four
tasks (underwear, pants, belt, and jacket), each of which must be
completed before the next one can begin.  These four tasks form a
\term{chain}.  In general, a chain in a poset $(A, \preceq)$ is a
sequence of distinct elements $a_1 \preceq a_2 \preceq \ldots \preceq
a_n$.  What we've just noted is that time to complete a poset of tasks
with an unlimited number of processors is at least the length of the
longest chain.  For this reason, the longest chain of tasks is also
called the \term{critical path}.

We've shown that the time to complete a poset of tasks is \textit{at
least} $t$, the length of the longest chain.  We're going to prove
that with an unlimited number of processors, there exists a way to
complete all the tasks time \textit{exactly} $t$.  There are a number
of ways to prove this; we'll use one that actually gives a $t$-step
schedule and yields lots of nice corollaries.  Here is the main
result:

\begin{theorem}
\label{th:parproc}
Given any finite poset $(A, \preceq)$ for which the longest chain has
$t$ elements, there exists a partition $A_1, A_2, \ldots, A_t$ of $A$
such that every predecessor of $a \in A_i$ is in $A_1 \cup \ldots \cup
A_{i-1}$.
\end{theorem}

Before we prove this, let's look at some implications.

\begin{corollary}
Every task in $A_i$ can be scheduled for step $i$.
\end{corollary}

This holds because every predecessor of a task $a \in A_i$ was
scheduled for a preceding time step.

\begin{corollary}
The number of steps required to complete a poset of tasks with an
unlimited number of processors is equal to the length of the longest
chain.
\end{corollary}

This follows because we can assign every task to one of $t$ time steps
where $t$ is the length of the longest chain.  Now let's go back and
prove the main theorem.

\begin{proof} (of Theorem~\ref{th:parproc})
Assign element $x \in A$ to subset $A_i$ where $i$ is the length of
longest chain with $x$ as a maximal element.  Let $b$ be a prececessor
of $a$; that is, $a \preceq b$ and $b \neq a$.

Now we argue by contradiction; suppose that $b \not\in A_1 \cup \ldots
\cup A_{i-1}$.  This means that there exists a chain of length greater
than $i - 1$ with $b$ as the maximal element.  But then adding $a$ to
this chain gives a chain of length greater than $i$ with $a$ as the
maximal element, contradicting the definition of $i$.
\end{proof}

\subsection{Chains and Antichains}

An elegant dual relationship holds for posets.  Recall that a
\term{chain} in a poset is a collection of elements which are all
\textit{comparable} to one another.  In contrast, an \term{antichain}
in collection of elements which are all \textit{incomparable}.  There
is an elegant dual relationship between chains and antichains:

\begin{theorem}
Let $(A, \preceq)$ be a finite poset.

\begin{enumerate}

\item $A$ can be partitioned into $t$ antichains, where $t$ is the
size of the largest chain.

\item $A$ can be partitioned into $s$ chains, where $s$ is the size of
the largest antichain.

\end{enumerate}
\end{theorem}

The first part of this theorem follows immediately from our analysis
of parallel scheduling.  Theorem~\ref{th:parproc} guarantees a
partition of $A$ into sets $A_1, \ldots, A_t$ such that every
predecessor of $a \in A_i$ is in $A_1 \cup \ldots \cup A_{i-1}$.  In
fact, these sets must be antichains; no set $A_i$ can contain
distinct, comparable elements.  We'll not prove the second part, which
is itself usally called Dilworth's Theorem.


\iffalse
\begin{theorem}
Every poset with $n$ elements has either a chain of length greater
than $t$ or an antichain of size at least $n / t$, where $t$ is any
positive integer.
\end{theorem}

\begin{proof}
There are two cases.

\underline{Case 1}. \quad If there is a chain of length greater than
$t$, then the claim is true.

\underline{Case 2}. \quad Otherwise, every chain has length at most
$t$.  Then the $n$ elements of the poset can be partitioned into at
most $t$ antichains.  These $t$ antichains can not all contain fewer
than $n / t$ elements; that would imply that they contain a total of
fewer than $t \cdot (n / t) = n$ elements.  Thus, some antichain
contains at least $n / t$ elements and the claim is again true.
\end{proof}

\begin{corollary}
Every $n$-element poset has a chain or antichain of size at least
$\sqrt{n}$.
\end{corollary}
\fi