Blog. Paper.

← All posts

Tasks, processes and connected graphs

What graph theory says about handing a job to a staff of agents.

Abstract. We model a job as a directed graph of tasks, in which an arrow means that one task needs the output of another, and a staff as an undirected graph of agents, in which an edge means that two agents can hand work to each other. For the task graph we collect classical results on how long a job must take, how many agents can work at once, and how much a careless order of work can cost. For the staff graph we collect results on when work can get from one agent to another and on what happens when an agent is missing. We prove the short results and work one example through.

1Two graphs

A job is a finite set \(T\) of tasks. Write \(u \to v\) when task \(v\) needs the output of task \(u\). The tasks and these arrows form a directed graph \(G = (T, E)\), the task graph. Each task \(v\) has a duration \(w(v) > 0\).

A staff is a finite set \(A\) of agents. Join two agents by an edge when one can hand work straight to the other. The agents and these edges form an undirected graph \(H = (A, F)\), the staff graph.

A process is a task graph that is run more than once, such as a hiring round or a month-end close. Each run is a job of the same shape, so whatever is proved about the graph holds for every run.

In a task graph every task has to be done, so the questions are about order and time. In a staff graph one route between two agents is enough, so the questions are whether a route exists and how many there are.

2When a job can be done at all

Proposition 1. A job can be completed if and only if its task graph has no directed cycle.

Proof. Suppose there is a cycle \(v_1 \to v_2 \to \dots \to v_k \to v_1\). Each task on it needs the output of the one before, so none of them can be the first to finish, and none is ever finished. Now suppose there is no cycle. Start at any task and step backwards along arrows. The walk never returns to a task it has visited, and \(T\) is finite, so it stops at a task that needs nothing. Do that task and delete it. What is left still has no cycle, so repeat until nothing is left. □

The order in which the proof does the tasks is a topological order. Kahn [6] finds one in time proportional to the size of the graph.

From here on \(G\) has no cycle. Write \(u \prec v\) when a directed path leads from \(u\) to \(v\), that is, when \(v\) needs \(u\) directly or through other tasks. Because there is no cycle, \(\prec\) is a strict partial order on \(T\). A chain is a set of tasks in which every two are related by \(\prec\). An antichain is a set in which no two are.

3How long a job must take

The duration of a chain is the sum of the durations of its tasks. Let \(L\) be the largest duration of any chain. A chain that reaches it is a critical path [7].

A schedule gives each task an agent and a start time. The agent works on the task without a break for its duration, an agent works on one task at a time, and a task does not start before every task it needs has finished. Any agent can do any task. A schedule finishes when its last task does.

Proposition 2. No schedule finishes before time \(L\), whatever the number of agents. With one agent for every task, the job can be finished at exactly \(L\).

Proof. If \(u \prec v\) then \(v\) cannot start before \(u\) has finished. The tasks of a chain therefore never overlap in time, and a critical path alone takes \(L\). For the second claim, start each task at the moment the last of the tasks it needs has finished. Let \(f(v)\) be the time at which \(v\) then finishes:

\[ f(v) = w(v) + \max_{u \to v} f(u), \]

where the maximum over no tasks is \(0\). Going through the tasks in a topological order, \(f(v)\) is the largest duration of a chain that ends at \(v\). The job finishes at \(\max_v f(v) = L\). □

4How many agents can be busy at once

Let the width \(\omega\) be the size of the largest antichain. The tasks in progress at any moment form an antichain, because related tasks never overlap in time. So at most \(\omega\) agents are ever busy at once.

Theorem 3 (Dilworth [1]). The smallest number of chains into which the tasks can be divided is \(\omega\).

At least \(\omega\) chains are needed, because two tasks of an antichain cannot share a chain. That \(\omega\) are enough is the content of the theorem, and we refer to [1] for the proof. Now give each chain to one agent. Then \(\omega\) agents cover the job, and within one agent's share each task builds on the one before.

Theorem 4 (Mirsky [9]). Let \(\ell\) be the number of tasks in the longest chain. The smallest number of antichains into which the tasks can be divided is \(\ell\).

Proof. Two tasks of a chain cannot share an antichain, so at least \(\ell\) antichains are needed. Give each task \(v\) a level: the number of tasks in the longest chain that ends at \(v\). If \(u \prec v\) then the level of \(u\) is smaller than the level of \(v\), so tasks of equal level form an antichain. The levels are \(1, \dots, \ell\). □

When every task takes one unit of time and there are enough agents, the job therefore takes \(\ell\) rounds: round \(i\) does the tasks of level \(i\).

5A fixed number of agents

Suppose there are \(m\) agents, and let \(W\) be the sum of all durations. Call a task ready when everything it needs has finished and it has not started. Call a schedule greedy when no agent is idle while a task is ready.

Theorem 5 (Graham [4]). Every greedy schedule on \(m\) agents finishes by time

\[ \frac{W}{m} + \Bigl(1 - \frac{1}{m}\Bigr) L. \]

No schedule on \(m\) agents finishes before \(\max(W/m,\, L)\), so a greedy schedule takes at most \(2 - 1/m\) times as long as the best one.

Proof. Let the schedule finish at time \(C\), and let \(v_1\) be a task that finishes then. If \(v_1\) needs other tasks, let \(v_2\) be one of them that finishes last, and continue in the same way down to a task \(v_k\) that needs nothing. Between the finish of \(v_{i+1}\) and the start of \(v_i\), the task \(v_i\) is ready and is not running, so all \(m\) agents are busy. The same holds before the start of \(v_k\). So whenever some agent is idle, one of \(v_1, \dots, v_k\) is running. These tasks form a chain, so such moments add up to at most \(L\), and during them at most \(m - 1\) agents are idle. Counting agent-time gives \(mC \le W + (m-1)L\). For the second claim, Proposition 2 gives \(L\), and \(m\) agents do at most \(m\) units of work in each unit of time, which gives \(W/m\). □

6A worked example

A hiring round has nine tasks. Durations are in units of time.

TaskNeedsDuration
aAgree the role and the criterianothing1
bWrite the job posta2
cBuild the application pagea3
dPublish the postb, c1
eWrite the screening questionsa2
fScreen the applicationsd, e4
gPlan the interviewsa2
hMake the shortlistf1
iInvite the shortlistg, h1
The task graph of the hiring round. Arrows run from a to b, c, e and g; from b and c to d; from d and e to f; from f to h; from h and g to i. a1 c3 b2 e2 g2 d1 f4 h1 i1
Figure 1. The task graph of the hiring round, with each duration above its task. The critical path is in gold.
  • The critical path is \(a, c, d, f, h, i\), so \(L = 1 + 3 + 1 + 4 + 1 + 1 = 11\). The total is \(W = 17\).
  • The longest chain has \(\ell = 6\) tasks. The levels of Theorem 4 are \(\{a\},\) \(\{b, c, e, g\},\) \(\{d\},\) \(\{f\},\) \(\{h\},\) \(\{i\}\).
  • The width is \(\omega = 4\), reached by \(\{b, c, e, g\}\). An antichain that contains \(a\) or \(i\) has one task, because \(a\) comes before every other task and \(i\) after. Any other antichain either avoids \(d\), \(f\) and \(h\), and so lies inside \(\{b, c, e, g\}\), or contains exactly one of them, which rules out \(b\) and \(c\) and leaves at most three tasks.
  • By Theorem 3 the tasks divide into four chains, for example \(\{a, c, d, f, h, i\},\) \(\{b\},\) \(\{e\},\) \(\{g\}\).

One agent takes \(17\). For two agents the lower bound of Theorem 5 is \(\max(17/2,\, 11) = 11\), and the first schedule in Figure 2 reaches it. It always starts the ready task that has the longest chain ahead of it. A second agent therefore saves six units and a third saves nothing, although four tasks could run at once after \(a\).

The second schedule in Figure 2 is also greedy. It starts \(g\) and \(e\) before \(b\) and \(c\) and finishes at \(13\). Theorem 5 gives at most \(17/2 + 11/2 = 14\) for any order the agents pick. We checked every greedy schedule of this job on two agents, and none finishes later than \(13\).

Two schedules on two agents. The first finishes at 11, the second at 13. Longest chain ahead first Agent 1 Agent 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a b c d e f g h i done at 11 g and e first Agent 1 Agent 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a b c d e f g h i done at 13 bound 14
Figure 2. Two greedy schedules of the hiring round on two agents. Tasks on the critical path are in gold. The dashed line is the bound of Theorem 5.

7Jobs in pieces

Ignore the direction of the arrows. \(G\) is connected when a path joins any two tasks. Otherwise it falls into connected components. A connected graph on \(n\) tasks has at least \(n - 1\) arrows.

Proposition 6. Tasks in different components are never related by \(\prec\). With one agent for every task, the job can be finished in the time its slowest component needs.

Proof. A directed path is a path, so related tasks lie in one component. Every chain therefore lies in one component, and \(L\) is the largest of the components' critical paths. □

Components can go to separate groups of agents that never need anything from each other. Work done for two people who have nothing to do with each other has no arrow between them, so the graph of everything in progress has at least one component for each such person. One person's long job can then delay another person's reply only by keeping agents busy, which is the \(m\) of section 5.

The order \(\prec\) also says what a change touches. For a task \(v\), let \(D(v) = \{x : v \prec x\}\). If the output of \(v\) changes, the tasks in \(D(v)\) have to be looked at again and no others. In the example \(D(e) = \{f, h, i\}\): new screening questions mean screening again, a new shortlist and new invitations.

8The staff graph

Let \(N\) be the number of agents. A route from one agent to another is a list of agents, none of them twice, in which each is joined to the next by an edge. Work can get from any agent to any other exactly when every two agents have a route between them, that is, when \(H\) is connected. That takes at least \(N - 1\) edges, and a connected graph with exactly \(N - 1\) is a tree. A tree has exactly one route between any two agents. A star is a tree in which one agent, the centre, is joined to every other agent. The distance between two agents is the number of edges on a shortest route between them.

Proposition 7. For \(N \ge 3\), the star is the only tree in which every two agents are within distance two.

Proof. Take a tree with all distances at most two. Since \(N \ge 3\) and the tree is connected, some agent \(c\) has at least two neighbours. Suppose another agent \(x\) is not a neighbour of \(c\). Then there is a route \(x, y, c\), and \(c\) has a neighbour \(z\) other than \(y\). A tree has one route between two agents, and from \(x\) to \(z\) it is \(x, y, c, z\), of length three. So every other agent is a neighbour of \(c\). That is already \(N - 1\) edges, so there are no more. □

In a star the centre lies on the route between every two of the other agents, which is \(\binom{N-1}{2}\) pairs. If the centre is missing, no two of the remaining agents are connected.

Theorem 8 (Menger [8]). Let \(x\) and \(y\) be two agents with no edge between them. The largest number of routes from \(x\) to \(y\), no two of which share an agent other than \(x\) and \(y\), equals the smallest number of agents other than \(x\) and \(y\) whose removal leaves no route from \(x\) to \(y\).

In a star that number is one for any two agents other than the centre. To raise it to two for every pair, each agent needs at least two neighbours, so the graph needs at least \(N\) edges. A ring is a single cycle through all the agents. It has exactly \(N\) edges, but its distances grow to \(\lfloor N/2 \rfloor\). A wheel is a star with a ring through the outer agents. It has \(2(N-1)\) edges and every distance in it is at most two, and for \(N \ge 5\) it stays connected until three agents are missing. In general, for \(2 \le k \le N - 1\), a graph that stays connected with any \(k - 1\) agents missing needs at least \(\lceil kN/2 \rceil\) edges, because every agent needs at least \(k\) neighbours, and Harary [5] showed that this many are enough.

Three staff graphs on nine agents: a star, a ring and a wheel. Star8 edges Ring9 edges Wheel16 edges
Figure 3. A star, a ring and a wheel, drawn with nine agents. The centre is in gold.

Staff has one assistant and twenty specialists, so \(N = 21\). The centre of a star on them lies between \(\binom{20}{2} = 190\) pairs.

Shape, \(N = 21\)EdgesLongest distanceMissing agents that disconnect it
Star2021
Ring21102
Wheel4023
Every pair joined2101none can

9Assigning tasks to agents

An assignment is a map \(\varphi : T \to A\) that says who does each task. An arrow \(u \to v\) with \(\varphi(u) \ne \varphi(v)\) is a handover, and it needs a route in \(H\) from \(\varphi(u)\) to \(\varphi(v)\).

In the example, one agent means no handovers and a job that takes \(W = 17\). Four agents, one for each chain of section 6, finish in \(L = 11\), and six of the eleven arrows become handovers. Splitting the tasks between two agents, the same number to each, with the fewest handovers is the minimum bisection problem, which is NP-hard [3], so in general the best split is found by search or approximated.

10What Staff does today

  • In mail every thread starts with the assistant. A handover passes the whole thread, and the colleague answers from then on. The assistant is used once for each thread, to choose who gets it.
  • Whoever holds a thread can copy in any colleague. For handovers the staff graph has every pair joined, so no two specialists depend on a third agent to reach each other.
  • In a call the assistant is the one who brings colleagues in, so there the graph is a star.
  • One agent answers a thread at a time. Over the life of a thread, the agents who held it form a walk in \(H\).

Staff does not compute any of the quantities above for anyone's job. The assistant decides who to copy in from the request and from what each specialist is for.

11What the model leaves out

The model makes four assumptions that real work does not meet.

Known durations. When durations are random, the expected finishing time is at least the \(L\) computed from average durations, because a maximum of sums is a convex function, and it is usually more [2].

A known graph. Tasks appear while the job is under way, for example a question for the person or a file that turns out to be missing. The results above describe the graph as it turned out, so most of them can be used only afterwards. Theorem 5 still holds while the job is running, provided every task is known by the moment the last task it needs has finished, or from the start when it needs nothing. A greedy schedule then needs to know only which tasks are ready now, and the proof uses nothing else. A task that appears later can break the bound. Take two agents, a task \(x\) of duration \(1\), and a task \(y\) of duration \(1\) that needs nothing and appears only when \(x\) finishes. The job ends at \(2\), and \(W/m + (1 - 1/m)L = 3/2\).

Interchangeable agents. Sections 3 to 6 let any agent do any task. If a task can go only to the specialist it is for, it can wait for that agent while others are idle, and Theorem 5 does not cover that case.

Free handovers. In practice the colleague reads the thread before doing anything. Giving each handover a delay turns section 5 into scheduling with communication delays, which is a harder problem.

Measuring real threads would show how far the model is off: the task graph as it turned out, its width and critical path, and the number of handovers.

References

  1. R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics 51 (1950), 161–166.
  2. D. R. Fulkerson. Expected critical path lengths in PERT networks. Operations Research 10 (1962), 808–817.
  3. M. R. Garey, D. S. Johnson and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science 1 (1976), 237–267.
  4. R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45 (1966), 1563–1581.
  5. F. Harary. The maximum connectivity of a graph. Proceedings of the National Academy of Sciences 48 (1962), 1142–1146.
  6. A. B. Kahn. Topological sorting of large networks. Communications of the ACM 5 (1962), 558–562.
  7. J. E. Kelley Jr. and M. R. Walker. Critical-path planning and scheduling. Proceedings of the Eastern Joint Computer Conference (1959), 160–173.
  8. K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10 (1927), 96–115.
  9. L. Mirsky. A dual of Dilworth's decomposition theorem. American Mathematical Monthly 78 (1971), 876–877.

All posts