Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 24, 2013

Project Scheduling and Copresheaves

Posted by Simon Willerton

Obsessed as I am with finding examples of enriched categories, I was struck by the unfamiliar notion of ‘activity network’ when checking a colleague’s course on graph theory. What struck me was how scheduling actives seemed to be like finding a certain kind of copresheaf. Activity networks are also known as PERT charts to people in project management: an activity network or PERT chart records all the dependencies between the activities need to be completed during a project, and also records the times the activities will take to complete. Once you have this information you can try to schedule each of the activities in so that the project is completed as quickly as possible, and you can identify which activities are critical in the sense that any delay in that activity will cause a delay to the whole project.

I noticed that there was some enriched category theory going on with these PERT charts. Patrons of the Café are probably familiar with the idea that metric spaces can be thought of as categories enriched over ([0,],,+)([0,\infty],\ge,+) the category of extended non-negative numbers. The triangle inequality for metric spaces then corresponds to the composition for enriched categories. The category that is enriched over for PERT charts is ({}[0,],,+)(\{-\infty\}\cup[0,\infty],\le,+) so the main difference is that the morphisms go the other way, this means that you get a reversed triangle inequality! However, that makes sense in the scheduling context. I will explain how this gives categorical interpretations of terms like earliest start time, latest start time, float and critical path.

I have stressed the project management aspects here, but these ideas are also important, it seems, in scheduling processor jobs in parallel computing.

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
aFix electrics7 days
bPlaster walls10 daysa
cLay carpets3 daysa
dPaper walls12 daysb
eRe-tile roof15 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
SStart0 days-
aFix electrics7 daysS
bPlaster walls10 daysa
cLay carpets3 daysa
dPaper walls12 daysb
eRe-tile roof15 daysS
FFinish0 daysd, 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.

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)T(x) to each activity xx so that whenever we have activity yy with an explicit dependency on xx we have the scheduling constraint.

(1)C(x,y)+T(x)T(y)C(x,y)+T(x)\le T(y)

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

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

C:A×AV.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:𝒜SetT\colon \mathcal{A}\to Set, so that means, of course, that to each object xx in 𝒜\mathcal{A} we associate a set T(x)T(x) and to each pair of elements xx and yy we have a function between sets T:Hom 𝒜(x,y)Hom Set(T(x),T(y))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

(2)Hom 𝒜(x,y)×T(x)T(y),Hom_{\mathcal{A}}(x,y)\times T(x)\to T(y),

where (f,α)T(f)(α)(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 {}[0,)\{-\infty\}\cup[0,\infty) into a category by using \le as a poset structure, so there is a unique morphism aba\to b if and only if aba\le b and using ++ as a monoidal structure. Note that this is the opposite to the category structure used on [0,][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)T(x)T(y)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𝒱v\in \mathcal{V} the functor vv\otimes{-} is left adjoint to [[v,]][[v,{-}]]. I’m using double brackets here not to confuse the internal hom [[a,b]][[a,b]] with the closed interval [a,b][a,b].

In our case this means we need

a+bcif and only ifa[[b,c]].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 {}[0,]\{-\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(,)a,b\in (-\infty,\infty) we define

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

I will often write bab-a instead of [[a,b]][[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 aa and bb are finite. (I can give a hint if people need help getting started.) + b + ? a a+b + + ? + +[[,]] b + ? ? ? a ? ba ? + ? ? ? \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 Semi-Continuous Entropy Functions, (10 MB file!) IMA reprint 86 (1984).

He calls categories enriched over ([0,],,+)([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 =({}[0,],,+)\mathcal{R}=(\{-\infty\}\cup[0,\infty],\le,+). Let’s just remind ourselves what such a thing is. It consists of a set AA and a function D:A×A{}[0,]D\colon A\times A\to \{-\infty\}\cup[0,\infty] such that

  • for all xAx\in A we have 0D(x,x)0\le D(x,x),
  • for all x,y,zAx,y,z\in A we have D(x,y)+D(y,z)D(x,z)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 AA, this just means it corresponds a function

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

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

D(x,y)max{C(x,a 1)+C(a 1,a 2)++C(a n1,a n)+C(a n,y)},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,,a nAa_1,\dots, a_n\in A and over all n0n\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 FF), so C(a,F)=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, ie D(a,F)=29D(a,F)=29.

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

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

The minimum time lag after starting xx to starting zz is at least as big as the minimum time lag from xx starting to yy starting plus the minimum time lag from yy starting to zz starting 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 xx we will mean setting a time T(x)[0,)T(x)\in [0,\infty) relative to the start of the project, so that T(S)=0T(S)=0, subject to the explicit constraints, so for all activities x,yAx,y\in A

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

This means that TT 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)(A,D) to \mathcal{R}. This is just expressing the free-forgetful functor between \mathcal{R}-graphs and \mathcal{R}-categories:

-Grph(A,U())-Cat(F(A),).\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)(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)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)D(S,x) – the evaluation of the representable copresheaf. As functions we have that the earliest start time is a copresheaf earliest start time=D(S,).\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 xx and the finish is D(x,F)D(x,F), and if the project is not delayed then the finish time is D(S,F)D(S,F), thus the latest start time is D(S,F)D(x,F)D(S,F)- D(x,F) or in internal hom terms [[D(x,F),D(S,F)]][[D(x,F),D(S,F)]]. So the latest start time is the copresheaf latest start time=[[D(,F),D(S,F)]].\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 xx is (D(S,F)D(x,F))D(S,x)=D(S,F)(D(x,F)+D(S,x))(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)]][[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 xx between SS and FF.

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

D(S,)T()[[D(,F),D(S,F)]]. 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, these are the paths in the PERT graph from the start to the finish which consist of activities with float zero, so a delay of any activity on the path will lead to a delay in the project. The path SabdFS a b d F is critical in our example above. Everywhere on a critical path the triangle inequality from SS to FF 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?

Posted at March 24, 2013 5:47 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2602

18 Comments & 0 Trackbacks

Re: Project Scheduling and Copresheaves

[Note: Tim emailed me this straight after a skim reading of the post and before drinking his morning coffee, so I take responsibility for posting this here. Simon.]

I liked the post. I used to teach critical path analysis, and then go on to discrete dynamical systems and (times) Petri nets. These both have strong categorical flavour.

Have you looked at the paper:

Casley, R.T., Crew, R.F., Meseguer, J., and Pratt, V.R., Temporal Structures, Proc. Category Theory and Computer Science 1989, ed. D. Pitt et al, LNCS 389, 21-51, Springer-Verlag, 1989. Revised journal version in Mathematical Structures in Computer Science, Volume 1:2, 179-213, July 1991. (The Journal version is good preprint pdf.)

(I think that is the right one of Pratt’s work. He has written a lot that is discursive so it is difficult to find which bit it is in.)

There are links between discrete dynamical systems approaches to scheduling and tropical algebra. I used to get students doing projects on using the Max+ / tropical algebra and linear algebra to attack fairly real life scheduling problems. That was good fun both for the students and for me! I learnt a lot!

The Petri nets aspect was explored by Meseguer, as a Petri net looks like a presentation of an symmetric monoidal category. Your post suggests that there may be an enriched version of his result for times Petri nets. (I had meant to explore that with students but the occasion never came, and the Bangor department was closed which made things impossible.) Meseguer’s papers include

José Meseguer, Ugo Montanari: Petri Nets Are Monoids: A New Algebraic Foundation for Net Theory. LICS 1988: 155-164

and another one on Petri nets and Linear Logic from about the same time. See Meseguer’s papers at dblp.

Posted by: Tim Porter on March 25, 2013 9:19 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Tim, thanks for these. I’ll have a look.

Last week I got hold of a copy of

Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications (Princeton Series in Applied Mathematics) Bernd Heidergott, Geert Jan Olsder, Jacob van der Woude.

They seem to take train scheduling as a key motivating example. I’m looking forward to chugging through it.

Posted by: Simon Willerton on March 26, 2013 5:40 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

As I said before, I found it a fun area to teach. Somehow it seems that you can persuade the students that the calculations and theory are (i) useful (ii) not too difficult as they mirror ordinary linear algebra, and (iii) the methods reveal a lot about the algebra that they use almost automatically since here if you try to go on `automatic pilot’ you start subtracting yet that is clearly a silly thing to do.

I would be great to see this introduced into a lot of undergraduate courses. (I usually used Stephan Gaubert’s notes as a basis. I put a link on the n-Lab…. I am also convinced that eventually the homotopical algebra of related things will become very important.)

Posted by: Tim Porter on March 29, 2013 7:05 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Here’s a link to the notes of Gaubert on discrete event systems: Introduction aux Systèmes Dynamiques à Événements Discrets.

I’ve realized that the PERT graphs above fall into the timed Petri net net. In fact they fall into the smaller net of timed event graphs.

Tim, you said to me (in an email) that you have been “trying to push the idea of modelling complex systems of various types by enriched categories for some time”. Is there somewhere where I can read about this, or have you just been doing it verbally?

Posted by: Simon Willerton on April 8, 2013 11:55 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Mostly verbally!! I did prepare some draft EPSRC proposals but then it became clear that I needed a publication trail in such areas. I had talked about enriching shape theory in something like that way, way back in the 1980s, and also had published some stuff on using Chu spaces in their more general form (i.e. with a richer set of `truth values’) for handling observations. This was then further pushed forward with the project work the students had done on Petri nets etc., but then time ran out as it was clear that Bangor was going to be shut down, and our work load was going up. I talked to the then computer scientists in Bangor at the time, but then they left!

I never felt that the work would get published so left it aside. The ideas were not ripe at that time and there was not the interest in them that there might be now.

Posted by: Tim Porter on April 9, 2013 6:33 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Of course, as soon as I saw my e-mail I saw a typo, (is that a version of Sod’s law?). It should be `(timed) Petri nets’, not (times)!

Posted by: Tim Porter on March 25, 2013 10:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Why the exotic-sounding word ‘copresheaf’ instead of the familiar one ‘functor’?

Posted by: Mike Shulman on March 25, 2013 12:43 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Good question. I guess one answer is that I have been thinking too much about presheaves and copresheaves recently, so forgot that copresheaf might sound exotic to some (or perhaps, to most).

My emphasis on the word ‘copresheaf’ rather than ‘functor’ is due to thinking of copresheaves as being akin to functionals (ie scalar-valued functions) and functors as being akin to more general functions – I’m reckoning that functionals are the most basic kind of function. I consider the enriching category 𝒱\mathcal{V} to be the ‘scalars’, so a copresheaf on 𝒞\mathcal{C} is just a scalar-valued functor 𝒞V\mathcal{C}\to {V}.

In retrospect ‘functor’ might have been a less scary word to use than ‘copresheaf’, but would miss the specificity.

Posted by: Simon Willerton on March 25, 2013 4:19 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

So can

D(x,y)max{C(x,a 1)+C(a 1,a 2)++C(a n1,a n)+C(a n,y)}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)\}

be thought of as a path integral? As in matrix mechanics for any rig, it seems there is ‘multiplication’ (here addition) along a path and summation (here max) across paths.

Posted by: David Corfield on March 26, 2013 9:43 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Yes. You can think of it like that. It is indeed a ‘sum’ over all ‘paths’ of a certain ‘product’.

You should compare it with the metric graph case if you haven’t already. Suppose you have a graph with edges marked with a given length, so if uu and vv are vertices at either end of an edge then there is a length L(u,v)[0,)L(u,v)\in [0,\infty). We can then get a metric on the vertex set VertVert by the ‘shortest path metric’. This is a free [0,][0,\infty]-category by the analogous construction to that which I did for PERT graphs: I will spell that out.

We can extend the edge lengths to a function L:Vert×Vert[0,]L\colon Vert \times Vert \to [0,\infty], ie a [0,][0,\infty]-grap, by L(u,v)L(u,v)\coloneqq \infty if uu and vv do not have an edge between them.

We think of [0,][0,\infty] as a monoidal catgory where we have a morphism aba\to b if and only if aba\ge b and the monoidal product is addition ++. The coproduct for this is min. So the free [0,][0,\infty]-category (Vert,d:Vert×Vert[0,])(Vert,\;d\colon Vert\times Vert \to [0,\infty]) on the [0,][0,\infty]-graph (Vert,L:Vert×Vert[0,])(Vert,\; L\colon Vert\times Vert \to [0,\infty]) is the shortest path metric:

d(u,v)min{L(u,a 1)+L(a 1,a 2)++L(a n1,a n)+L(a n,v)}.d(u,v)\coloneqq min\{L(u,a_1)+L(a_1,a_2)+\dots +L(a_{n-1},a_n)+L(a_{n},v)\}.

This is again a ‘path integral’ in the sense you describe it.

Posted by: Simon Willerton on March 26, 2013 3:50 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Your

C(x,y)+T(x)T(y) C(x,y)+T(x)≤T(y)

is very much like your bakery example of optimal transport

ϕ(Hovis)>ϕ(Warburtons)+d(Warburtons,Hovis). \phi(Hovis)\gt \phi(Warburtons)+d(Warburtons,Hovis).

Posted by: David Corfield on March 26, 2013 10:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

Indeed, it is very much like the bakery example. The condition I want satisfied there is the negation of the inequality you give, so I want

d(Warburtons,Hovis)+ϕ(Warburtons)ϕ(Hovis).d(Warburtons, Hovis)+ \phi(Warburtons) \ge \phi(Hovis).

Thus ϕ\phi is a copresheaf on the metric space of bakeries. I seemed to have claimed back then that it was a presheaf, but I think I got the variance wrong. I’ll talk you through this a bit further below.

Why do I get the opposite inequality here to the scheduling case where I claimed that a copresheaf is something which satisfies

C(x,y)+T(x)T(y)?C(x,y)+ T(x)\le T(y)?

That’s because PERT graphs are related to categories enriched over a poset of extended non-negative real numbers with \le and metric spaces are categories enriched over a poset of extended non-negative reals with \ge.

Let’s remind ourselves what a copresheaf is. Suppose 𝒱\mathcal{V} is a closed monoidal category. For 𝒞\mathcal{C} a 𝒱\mathcal{V}-enriched category a presheaf on 𝒞\mathcal{C} is a 𝒱\mathcal{V}-functor T:𝒞𝒱T\colon \mathcal{C}\to \mathcal{V}. This means that it consists of a function on objects T:ob(𝒞)ob(𝒱)T\colon ob(\mathcal{C})\to ob(\mathcal{V}), and for each pair of objects x,yob(C)x,y \in ob({C}) there is a morphism in 𝒱\mathcal{V}

Hom 𝒞(x,y)Hom 𝒱(T(x),T(y)).Hom_{\mathcal{C}}(x,y) \to Hom_{\mathcal{V}}(T(x),T(y)).

Here Hom 𝒱Hom_{\mathcal{V}} means the internal hom in 𝒱\mathcal{V}. Because 𝒱\mathcal{V} is closed we have the hom-tensor adjunction in 𝒱\mathcal{V} so the morphism above is equivalent to a morphism in 𝒱\mathcal{V}

Hom 𝒞(x,y)T(x)T(y).Hom_{\mathcal{C}}(x,y)\otimes T(x) \to T(y).

If we are taking 𝒱\mathcal{V} a poset of real numbers with addition as the monoidal structure, then the \otimes becomes a ++ and the existence of a morphism in 𝒱\mathcal{V} of the form aba\to b just means aba \ge b or aba\le b depending on which partial order on the reals we have taken.

In the \le case the copresheaf condition is

Hom 𝒞(x,y)+T(x)T(y),Hom_{\mathcal{C}}(x,y) + T(x) \le T(y),

which is what we see for PERT graphs.

On the other hand, in the \ge case (ie the case relevant for metric spaces) the copresheaf condition is

Hom 𝒞(x,y)+T(x)T(y),Hom_{\mathcal{C}}(x,y) + T(x) \ge T(y),

which is what we saw for the bakeries.

Posted by: Simon Willerton on April 1, 2013 6:41 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

What I always dreamed of was a nice piece of shiny machinery (matrix mechanics) with a dial for you to choose your rig, and off it would go pumping out results on classical, quantum, statistical mechanics, homotopy theory, and now maybe optimal transport and project scheduling.

There was also the hope that rig morphisms would allow us to relate these areas, e.g., if a classical particle can get from A to B in a space, it means A and B are path connected.

Posted by: David Corfield on April 2, 2013 1:57 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

An interesting question in this regard is to whether or not a given rig RR can be categorified in the sense of finding a monoidal category whose set of (isomorphism class) of objects in the underlying set of RR, whose monoidal product on objects becomes the product in the rig and whose categorical coproduct becomes the addition in the rig.

By the above we can do that for (,max,+)(\mathbb{R},max,+) and (,min,+)(\mathbb{R},min,+). We can also do that for (,+,×)(\mathbb{N},+,\times) by taking the category of finite sets with the monoidal product being the cartesian product. But can we categorify ([0,],+,×)([0,\infty],+,\times)?? That would allow us to do proper(ish) path integrals in this enriched setting.

Posted by: Simon Willerton on April 2, 2013 2:48 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

We had plenty of discussion over the years of using tame groupoids with obvious sum and product as a categorification of the non-negative reals. Of course, any given real will have many different representations as a groupoid cardinality.

We even wondered about a ‘distance’ between groupoids.

Posted by: David Corfield on April 2, 2013 3:10 PM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

David wrote:

What I always dreamed of was a nice piece of shiny machinery (matrix mechanics) with a dial for you to choose your rig, and off it would go pumping out results on classical, quantum, statistical mechanics, homotopy theory, and now maybe optimal transport and project scheduling.

We basically came up with it; the links you assembled explain it. But I guess we’d have to write things up a bit more formally, preferably all in one place, for people to see that this machinery really exists.

When I saw Simon in Sheffield last week, he showed me the book Max Plus at Work, a rather down-to-earth introduction to the max-plus rig and its applications to train scheduling. It has a nice section on ‘timed Petri nets’ which, I realized, are just like the ‘stochastic Petri nets’ I love except that they use the max-plus rig instead of the rig of nonnegative reals with their ordinary addition and multiplication. So, chemical reaction theory is a deformation of train scheduling!

I wanted to write a paper explaining this then and there, and Simon sounded interested, so maybe we’ll do it. But he seems a bit more interested in enriching categories over different monoidal categories, while I seem a bit more interested in linear algebra over different rigs (or rig categories). So we may not be seeing eye-to-eye yet. They should be closely related, of course.

Posted by: John Baez on April 5, 2013 2:02 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

…chemical reaction theory is a deformation of train scheduling!

Excellent!

I wanted to write a paper explaining this then and there…

It would be great to revisit the ideas we all had in this area. No doubt they’re quite scattered. I just came across Urs talking about path length and path integral.

Posted by: David Corfield on April 5, 2013 8:34 AM | Permalink | Reply to this

Re: Project Scheduling and Copresheaves

John, I do like your overstated, as opposed to British understated, comments.

I wanted to write a paper […] then and there.

Ah, I didn’t realize.

There’s a link to the Max Plus at Work book above – the link points to the publisher rather than to Amazon as I’m trying to avoid Amazon at the moment due to their anti-social tax avoidance methods. (Note: there is a certain amount of British understatement in that last sentence.)

Posted by: Simon Willerton on April 9, 2013 11:40 AM | Permalink | Reply to this

Post a New Comment