\(\def\PR{\mathbb P} \def\EXP{\mathbb E} \def\reals{\mathbb R}\)
There are \(n\) jobs to be processed by a single machine. Processing job \(i\) takes a random time \(S_i\). Let \(μ_i = \EXP[S_i] < ∞\). A cost \(c_i\) is incurred per unit time until job \(i\) is completed.
For example, suppose there are two jobs, and completing job \(1\) and \(2\) took \(s_i\) and \(s_2\) time units respectively. If the processing order was \(\{1,2\}\), then the cost incurred is \(c_1 s_1 + c_2 (s_1 + s_2)\). If the processing order was \(\{2,1\}\), then the cost incurred is \(c_2 s_2 + c_1 (s_1 + s_2)\).
In what order should the jobs be processed so as to minimize the total expected cost?
A prisoner wishes to escape from a prison. There are \(n\) passages that leads out of the prison, some of them are dead-ends, others have guards, and remaining are unguarded are lead outside the prison. More precisely, passage \(i\) might be a dead-end with probability \((1-p_i-q_i)\), might have a guard with probability \(q_i\), and might be unguarded and lead outside the prison with probability \(p_i\). Thus, if the prisoner tries passage \(i\), he will find that the passage is a dead-end with probability \((1-p_i-q_i)\) and he can come back and try other passages; he will be captured by a guard with probability \(q_i\), and he will escape with probability \(p_i\). In what order should the prison test different passages if he wishes to maximize his probability of eventual escape? Does the optimal search order change if his objective is to minimize the probability of capture?
Let \(\pi\) and \(\mu\) be probability mass functions on the set \(\{1, \dots, n\}\). Let \(P\) and \(M\) be the corresponding cumulative mass functions, i.e., for any \(k \in \{1, \dots, n\}\) \[ M_k = \sum _ {i = 1} ^ {k } \mu _ i, \quad P_k = \sum _ {i = 1} ^ {k } \pi _ i.\]
Let \(\pi \ge_{r} \mu\). Show that for any \(k \in \{1, \dots, n\}\) \[ \frac { 1 - P_k} {1 - M_k} \ge \frac {\pi_k}{\mu_k} \ge \frac {P_k}{M_k}.\]
Use the previous part to show that \[ \pi \ge_r \mu \implies \pi \ge_s \mu.\]