Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
What's your question? –  MJD Jan 18 '13 at 3:20
    
I am trying to think of a realistic scenario i.e a job scheduling problem where this inequality doesn't necessarily hold –  zxcvbnm Jan 18 '13 at 3:35
1  
@zxcvbnm What does $t_{ij}$ represent in a job scheduling problem? How does it depend on $i$ and $j$? What do $i$ and $j$ represent, jobs or machines? In other words, what's your question? –  Erick Wong Jan 18 '13 at 5:18
    
t as in time from i to j as in start to finish –  zxcvbnm Jan 18 '13 at 5:38
    
Would you be able to provide a reference to where this is defined? Ideally one where there is an example of an instance of a "job-scheduling problem". –  Douglas S. Stones Jan 18 '13 at 9:39
add comment

1 Answer

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.