The n-Category Café

PERT graphs and project management

In project management, a project, for example renovating a house, will consist of various activities which need scheduling subject to various interdependencies between them. For instance, in the house example, you can’t get a decorator to paper the walls until you’ve had a plasterer plaster them and it takes, say, ten day to plaster the walls. There are standard methods to approach the scheduling of jobs. According to Wikipedia, the method of Program Evaluation and Review Technique (PERT) – closely associated to the critical path method –was introduced by the US Navy in the mid-twentieth century during the Polaris missile development and had precursors in the management of the Manhattan Project.

The PERT method begins with you writing down every activity you need to complete, how long each activity will take and which activities need which others to be finished. So, ignorant of anything to do with house renovation, let’s make up an example.

Label	Activity	Duration	Requires
a	Fix electrics	7 days
b	Plaster walls	10 days	a
c	Lay carpets	3 days	a
d	Paper walls	12 days	b
e	Re-tile roof	15 days

Note that we’ve only put in the explicit dependencies, so that although papering the walls (activity d) also requires the fixing of electrics (activity a) to be finished we don’t put that in.

We add specific start and finish activities, which we will label S and F. Activity F has no duration and is explicitly dependent on everything which didn’t have anything dependent on it – you can’t finish before everything is completed. Activity S has no duration, is not dependent on anything and any activity which is not already dependent on something is made dependent on S – nothing can begin before the start.

Label	Activity	Duration	Requires
S	Start	0 days	-
a	Fix electrics	7 days	S
b	Plaster walls	10 days	a
c	Lay carpets	3 days	a
d	Paper walls	12 days	b
e	Re-tile roof	15 days	S
F	Finish	0 days	d, c, e

We can now draw a graph of this data. We draw a node for each activity and and arrow for each explicit dependency. Each arrow is labelled by the amount of time after the first activity has started that the second activity can start – here we are measuring time in days. This is the basis of what is called a PERT chart.

Those of you who have filled in grant applications may have been asked to provide a PERT chart. Now you know, more-or-less, what one is. Often they are also labelled with things such as ‘earliest start time’, ‘latest start time’ and ‘float’, but we’ll come to those below.

Scheduling and copresheaves?

The goal of drawing up a PERT chart is to schedule the work, for instance book the contractors, so that the project finishes as quickly as possible. This means we wish to assign a start time $T(x)$ to each activity $x$ so that whenever we have activity $y$ with an explicit dependency on $x$ we have the scheduling constraint.

where $C(x,y)$ is the label on the arrow in the above PERT chart, so $C(x,y)$ is how long after $x$ starts that $y$ can start.

Actually we can give ourselves such scheduling constraints (1) on the start times $T(x)$ and $T(y)$ for every pair $x$ and $y$, not just those with those with arrows between them, by setting $C(x,y)=-\infty$ if there is no arrow from $x$ to $y$ in the graph, i.e. if there is no explicit dependency of $y$ on $x$. If we take $A$ to be our set of activities (including the start and finish activities) and $V$ to be the set $\{-\infty\}\cup [0,\infty)$, then we have encoded the dependencies and times as a $V$-graph $C$, on the set $A$, this just means that we have a function

$$C\colon A\times A\to V.$$

I’ve obviously been thinking too much about enriched categories of late as the scheduling constraint (1) looks to me like a copresheaf condition. Remember that a copresheaf on an ordinary category $\mathcal{A}$ is functor $T\colon \mathcal{A}\to Set$, so that means, of course, that to each object $x$ in $\mathcal{A}$ we associate a set $T(x)$ and to each pair of elements $x$ and $y$ we have a function between sets $T\colon Hom_{\mathcal{A}}(x,y)\to Hom_{Set}(T(x),T(y))$, or to put it another way, we have a morphism in the category of sets

where $(f,\alpha)\mapsto T(f)(\alpha)$. Compare this with the scheduling constraint (1).

Closed monoidal structure

To make this similarity into something more formal we can make $\{-\infty\}\cup[0,\infty)$ into a category by using $\le$ as a poset structure, so there is a unique morphism $a\to b$ if and only if $a\le b$ and using $+$ as a monoidal structure. Note that this is the opposite to the category structure used on $[0,\infty]$ to define metric spaces as enriched categories – there we use $\ge$. This means we can write the scheduling constraint (1) as the morphism

$$C(x,y)\otimes T(x)\to T(y)$$

which now looks more like the set copresheaf situation (2).

If we are enriching over a monoidal category $(\mathcal{V},\otimes)$ and want to talk about $\mathcal{V}$-functors into $\mathcal{V}$ then we will need to give $\mathcal{V}$ a $\mathcal{V}$-category structure, thiat is to say we will need that $\mathcal{V}$ is a closed monoidal category. This means we need a functor $[[{-},{-}]]\colon \mathcal{V}\times \mathcal{V}\to \mathcal{V}$ such for each $v\in \mathcal{V}$ the functor $v\otimes{-}$ is left adjoint to $[[v,{-}]]$. I’m using double brackets here not to confuse the internal hom $[[a,b]]$ with the closed interval $[a,b]$.

In our case this means we need

$$a+b\le c \qquad\text{if and only if} \qquad a\le [[b,c]].$$

In order to do this we will have to add a plus infinity, so we will define the category $\mathcal{R}$ to be $\{-\infty\}\cup[0,\infty]$ with $\le$ giving the morphisms and $+$ being the monoidal structure. It is easy to say what the closed structure is on finite numbers, so for $a,b\in (-\infty,\infty)$ we define

$$[[a,b]]=\begin{cases} b-a& a\le b,\\ -\infty& a\gt b\end{cases}$$

I will often write $b-a$ instead of $[[a,b]]$ with the understanding that it means $-\infty$ if you get a negative answer.

Exercise: How do the monoidal and closed structures extend to include infinite numbers? Fill in the following tables, where $a$ and $b$ are finite. (I can give a hint if people need help getting started.) $$\begin{matrix} +& \color{red}{-\infty} &\color{red}{b}& \color{red}{+\infty} \\ \color{red} -\infty& -\infty&-\infty&?\\ \color{red} a &-\infty& a+b & +\infty\\ \color{red}+\infty&?&+\infty&+\infty \end{matrix} \qquad\qquad\qquad\qquad \begin{matrix} [[,]]& \color{red}{-\infty} &\color{red}{b}& \color{red}{+\infty} \\ \color{red} -\infty& ?&?&?\\ \color{red} a &?& b-a & ?\\ \color{red}+\infty&?&?&? \end{matrix}$$

If I’d put negative numbers in as well (which I don’t think are necessary here) then I would have used ordinary subtraction between finite numbers. This is what Lawvere does when he puts this closed monoidal structure on $[-\infty,\infty]$, the whole of the extended real numbers, in his entropy paper:

State Categories, Closed Categories, and the Existence of Semi-Continuous Entropy Functions, (10 MB file!) IMA reprint 86 (1984).

He calls categories enriched over $([0,\infty],\le,+)$ ‘entropic categories’. I haven’t fully digested what use he makes of them in this paper.

Enriching over $\mathcal{R}$

We can now consider categories enriched over the closed monoidal category $\mathcal{R}=(\{-\infty\}\cup[0,\infty],\le,+)$. Let’s just remind ourselves what such a thing is. It consists of a set $A$ and a function $D\colon A\times A\to \{-\infty\}\cup[0,\infty]$ such that

• for all $x\in A$ we have $0\le D(x,x)$,
• for all $x,y,z\in A$ we have $D(x,y) +D(y,z)\le D(x,z)$.

This last condition looks bizarre as it is the triangle inequality the wrong way round! However, we will make sense of it in if we look at our scheduling example. Our PERT chart, illustrating the explicit dependencies between events, can be thought of as an $\mathcal{R}$-graph on the set $A$, this just means it corresponds a function

$$C\colon A\times A \to \{-\infty\}\cup[0,\infty]$$

We can form the free $\mathcal{R}$-category on $A$ by defining

$$D(x,y)\coloneqq max\{C(x,a_1)+C(a_1,a_2)+\dots +C(a_{n-1},a_n)+C(a_{n},y)\},$$

where the maximum is taken over all the tuples $a_1,\dots, a_n\in A$ and over all $n\ge 0$. (Here max is the coproduct in $\mathcal{R}$.) This $\mathcal{R}$-category is now recording the implicit dependencies. So for instance in the example above we didn’t record any explicit dependency between fixing the electrics (activity a) and finishing the project (activity $F$), so $C(a,F)=-\infty$ but it is a consequence of the other dependencies that you need to fix the electrics at least twenty nine days before finishing the project, i.e. $D(a,F)=29$.

I hope that if we interpret $D(x,y)$ as the time lag between starting activity $x$ and starting activity $y$, you can now make sense of the reversed triangle inequality

$$D(x,y) +D(y,z)\le D(x,z).$$

The minimum time lag after starting $x$ to starting $z$ is at least as big as the minimum time lag from $x$ starting to $y$ starting plus the minimum time lag from $y$ to starting $z$.

So we can think of the hom-objects in an $\mathcal{R}$-category as being like minimum possible time lags rather than minimum possible distances.

Scheduling and copresheaves

We can now return to the scheduling question. We want to schedule the activities in our project subject to the dependencies between them. Here by scheduling an activity $x$ we will mean setting a time $T(x)\in [0,\infty)$ relative to the start of the project, so that $T(S)=0$, subject to the explicit constraints, so for all activities $x,y\in A$

$$C(x,y)\le T(y)-T(x).$$

This means that $T$ is precisely an $\mathcal{R}$-graph function from out PERT chart to the underlying $\mathcal{R}$-graph of $\mathcal{R}$. This is corresponds exactly to an $\mathcal{R}$-functor from the free $\mathcal{R}$-category $(A,D)$ to $\mathcal{R}$. This is just expressing the free-forgetful functor between $\mathcal{R}$-graphs and $\mathcal{R}$-categories:

$$\mathcal{R}\text{-Grph}(A, U(\mathcal{R}))\cong \mathcal{R}\text{-Cat}(F(A),\mathcal{R}).$$

In other words, scheduling the jobs means finding a copresheaf on the $\mathcal{R}$-category $(A,D)$ of implicit dependencies.

We can give some categorical interpretations of standard ideas in critical path analysis now.

What we really want to do is to finish the project as quickly as possible. The shortest amount of time the project will take to finish is the minimum time lag between the start and the finish, this is just $D(S,F)$. Given that length of time, we want to know how much freedom we have in scheduling individual activities and whether delaying a specific activity will cause the whole project to be delayed – will it matter if the plasterer doesn’t turn up on time or the walls take longer to dry out than expected. There are three basic things then to know about each activity: the earliest start time, the latest start time, and the float.

• The earliest start time of an activity is hopefully self-explanatory. It is the minimum time lag between the start of the project and the start of the activity. In categorical terms it is just $D(S,x)$ – the evaluation of the representable copresheaf. As functions we have that the earliest start time is a copresheaf $$\text{earliest start time} =D(S,{-}).$$

• The latest start time of an activity is the latest that an activity can start without delaying the whole project. The minimum time lag between the activity $x$ and the finish is $D(x,F)$, and if the project is not delayed then the finish time is $D(S,F)$, thus the latest start time is $D(S,F)- D(x,F)$ or in internal hom terms $[[D(x,F),D(S,F)]]$. So the latest start time is the copresheaf $$\text{latest start time}=[[D({-},F),D(S,F)]].$$

• The float of an activity is the difference between its earliest start time and its latest start time, and so reflects how much leeway you have in scheduling the activity. If the float is zero then the activity is said to be critical. In our notation the float of activity $x$ is $(D(S,F)- D(x,F))-D(S,x)=D(S,F)-( D(x,F)+D(S,x) )$ or in the internal hom notation $$[[D(S,x) + D(x,F) ,D(S,F)]]$$ To put it another way, the float is measuring how much the reverse triangle equality is violated for $x$ between $S$ and $F$.

A viable schedule $T$ will be one which finishes the project as soon as possible and satisfies the constraints so will be a copresheaf which satisfies

$$D(S,{-})\le T({-}) \le[[D({-},F),D(S,F)]].$$

I don’t know if that is a condition which crops up elsewhere in category theory.

A further important notion is that of critical path: this is a path in the PERT graph from the start to the finish which consists of activities with float zero, so a delay of any activity on the path will lead to a delay in the project. The path $S a b d F$ is critical in our example above. Everywhere on a critical path the triangle inequality from $S$ to $F$ is actually an equality, so critical paths are the analogues of geodesics in metric spaces.

Further questions

All of this came out of me looking at a colleague’s course and thinking randomly “Hmm. That looks categorical.” Here are some random further questions.

1. Do other categorical notions have useful interpretations in this context? Is the notion of $\mathcal{R}$-functor between projects meaningful? How about the notion of $\mathcal{R}$-profunctor?

2. Is it useful to think of these things are ‘generalized metric spaces with negative distances’?

3. Do these ideas extend to other networks such as Petri nets or networks of resistors?

4. Does it help to think in terms of entropy as in Lawvere’s paper?