job-scheduling problem whose costs do not obey the triangle inequality

Question

For traveling salesman problems involving physical distances, one often has the “triangle inequality”: If $i, j,$ and $k$ represent three cities, then the distance $d_{ij}$ from $i$ to $j$ naturally satisfies

$$ d_{ij} ≤ d_{ik} + d_{kj}.$$

The analogous inequality might not hold for $t_{ij}$ in job-scheduling problems. I am supposed to try to come up with a realistic scenario in which it would not hold but I can't quite think of one.

What is a realistic example of a job-scheduling problem in which the triangle inequality does not hold for the costs?

Answer 1

If $i$,$j$, and $k$ represent three cities, then consider $t_{ij}$ which is the time is takes to work out what the fastest route from city $i$ to city $j$ is. (For example, by doing an $A^*$ search, the more roads we have to consider the longer it takes).

If there are direct high-speed roads joining $k$ to both $i$ and $j$ then $t_{ik}$ and $t_{kj}$ will be very small. (It will take very little time to prove that these roads provide the fastest route).

However, the fastest route from $i$ to $j$ may not go via $k$, so this information is not at all useful, and the time $t_{ij}$ to compute the fastest route could easily be greater then $t_{ik} + t_{kj}$.