Trading time for work; does this concurrency phenomenon have a name?

Question

Recently, my girlfriend and I were trying to get out of the house, when I encountered a phenomenon which I thought might be analogous to a tradeoff in concurrent systems.

Here's the real world setup.

Processes

• Process A: Girlfriend orders coffee on phone.
• Process B: Girlfriend gets ready at apartment, and ideally drives car to pick me up at coffee shop.
• Process C: I fetch coffee, and ideally get picked up by girlfriend at coffee shop.
• Process D: We commute together.

Dependencies

• Process A must complete before Processes B and C.
• Process B and C must complete before Process D.

Phenomenon

On the day:

• My girlfriend orders coffee (Process A) and begins getting ready (Process B).
• I leave the apartment to fetch coffee while my girlfriend is getting ready (Process C).
• However, my girlfriend takes longer than expected to get ready, so instead of getting picked up at the coffee shop shortly after dealing with payment, I wait.
• Then, we commute (Process D).

What's suboptimal?

Resources, namely me walking, are not used minimally. In retrospect, we determine the optimal solution given the knowledge that my girlfriend will take longer to get ready is to simply wait. Once she finishes getting ready, we ought to drive to the coffee shop together to fetch the coffee and commute from there.

Processes are appropriately recognized as able to be parallelized. But, because of resource sharing, will only yield the desired improvements under ideal circumstances wherein girlfriend arrives by car at coffee shop shortly after coffee has been fetched. Unless this circumstance is realized, the time to complete Processes A - D becomes primarily determined by Process B and optimization of Process C is not concerning.

More generally, we determine a sequential solution makes better use of resources than the concurrent solution.

If processes are performed...

A -> B -> C -> D

we will most likely prefer that outcome to the original...

     -> B - 
A - |      | -> D
     -> C -

... (in part) because, even though time is slightly less optimized, work is better shared.

Does this phenomenon have a name? In what areas of computing might this tradeoff be more common or concerning? What are common software analysis strategies that may help?

Note: I can contrive examples with more significant effects, even ones that do not produce optimal runtime (though that may be another phenomenon). But, (a) this is partially a playful barb at my gf's planning and (b) I thought this might resonate with some folks.

Answer 1

Such considerations are known as Critical Path analysis. They allow to describe the temporal dependencies and find the fastest solution, as well as detect bottlenecks or near-bottlenecks.

https://en.wikipedia.org/wiki/Critical_path_method

Answer 2

So your situation in computing terms: You have two task A and B that could be calculated in parallel. A produces a result X at no cost at the end of A. B requires X at the first step. B has the choice of waiting for A to finish, or calculating X itself.

It is not uncommon that trying to parallelise tasks involves duplicating some work. There is no particular name for this.

(A much worse case is the alpha-beta algorithm for chess. Each calculation makes the next calculation more efficient. But if you perform multiple calculations in parallel, you can’t take advantage of that).

Answer 3

In the absence of a direct answer, here are some ideas.

I would say this is essentially a job scheduling problem with multiple optimization criteria:

• total completion time
• resource utilization

The mathematical discipline that studies such problems is scheduling theory, a subdiscipline of operations research; I'm not really familiar with the field, but if you're looking for standard terminology, I'd look there.

Many others have been working on scheduling problems, with their own approach, and no doubt some of them have their own terminology.

For instance, I used to work on a Petri net editor that can be used to draw your examples (as Petri nets), and, after assigning expected processing times to the individual tasks, simulations can be run to calculate average completion times and resource utilization for each resource. It is by no means the only software tool with such capabilities. Its designer, a professor in computer science (now retired), spent considerable effort on problems in logistics and job scheduling, and this was one of his efforts to provide practical tooling for modeling and optimizing such problems. This approach is different from the one taken in operations research, and it has its own merits and limitations.