Question

There are three jobs that need to be processed, with the processing time of job \(i\) being exponential with rate \(\mu_{i} .\) There are two processors available, so processing on two of the jobs can immediately start, with processing on the final job to start when one of the initial ones is finished. (a) Let \(T_{i}\) denote the time at which the processing of job \(i\) is completed. If the objective is to minimize \(E\left[T_{1}+T_{2}+T_{3}\right]\), which jobs should be initially processed if \(\mu_{1}<\mu_{2}<\mu_{3} ?\) (b) Let \(M\), called the makespan, be the time until all three jobs have been processed. With \(S\) equal to the time that there is only a single processor working, show that $$ 2 E[M]=E[S]+\sum_{i=1}^{3} 1 / \mu_{i} $$ For the rest of this problem, suppose that \(\mu_{1}=\mu_{2}=\mu, \quad \mu_{3}=\lambda .\) Also, let \(P(\mu)\) be the probability that the last job to finish is either job 1 or job 2, and let \(P(\lambda)=1-P(\mu)\) be the probability that the last job to finish is job 3 . (c) Express \(E[S]\) in terms of \(P(\mu)\) and \(P(\lambda)\). Let \(P_{i, j}(\mu)\) be the value of \(P(\mu)\) when \(i\) and \(j\) are the jobs that are initially started. (d) Show that \(P_{1,2}(\mu) \leqslant P_{1,3}(\mu)\). (e) If \(\mu>\lambda\) show that \(E[M]\) is minimized when job 3 is one of the jobs that is initially started. (f) If \(\mu<\lambda\) show that \(E[M]\) is minimized when processing is initially started on jobs 1 and \(2 .\)

Short answer

To minimize the expected total completion time, we should initially process the two jobs with the smallest rates, in this case, \(\mu_1\) and \(\mu_2\). Furthermore, we have the following results: 1. \(2 E[M] = E[S] + \sum_{i=1}^{3} \frac{1}{\mu_i}\). 2. \(E[S] = P(\mu) E[S\mid \text{last job is } 1 \text{ or } 2] + P(\lambda) E[S\mid \text{last job is } 3]\). 3. \(P_{1,2}(\mu) \leq P_{1,3}(\mu)\). When \(\mu > \lambda\), we should start processing jobs 1 and 3 initially to minimize E[M]. On the other hand, when \(\mu < \lambda\), we should start processing jobs 1 and 2 initially to minimize E[M].

Step-by-step solution

(a) Minimizing Expected Completion Time

To minimize the expected total completion time, we should start processing the two jobs with the smallest rates (\(\mu_1\) and \(\mu_2\) in this case). If we do so, the total expected completion time for all jobs will be smaller than for any other combination. When one of them is finished, the remaining job with the higher rate will start processing. Following this approach, the expected total completion time is minimized.

(b) Finding the relationship between Makespan and other variables

First, let's denote the processing times for jobs \(i = 1, 2, 3\) as \(X_i\), where \(X_i\) is an exponential random variable with rate \(\mu_i\). We have two processors, so let's denote the processing times for each processor as \(P_1\) and \(P_2\). Now, we know that the makespan, \(M\), is the maximum of the two processing times for each processor. Therefore, we can write \(M = \max(P_1, P_2)\). Notice that: 1. The total processing time is the sum of all individual processing times: \(P_1 + P_2 = X_1 + X_2 + X_3\). 2. The time with only one processor working is the difference between the total processing time and the makespan: \(S = (P_1 + P_2) - M\). Using these two observations, we can find the expected value of the makespan: $$ 2 E[M] = E[P_1 + P_2 - S] + E[P_1 + P_2] = E[P_1 + P_2] - E[S] + E[P_1 + P_2]. $$ Recall that \(P_1 + P_2 = X_1 + X_2 + X_3\). Thus, we can write: $$ 2 E[M] = E[X_1 + X_2 + X_3] - E[S] + E[X_1 + X_2 + X_3]. $$ Since expectations are additive, we get: $$ 2 E[M] = E[S] + \sum_{i=1}^{3} \frac{1}{\mu_i}. $$

(c) Express E[S] using probabilities

We are given that \(\mu_1 = \mu_2 = \mu\) and \(\mu_3 = \lambda\). Also, let \(P(\mu)\) be the probability that the last job to finish is either job 1 or job 2, and let \(P(\lambda) = 1 - P(\mu)\) be the probability that the last job to finish is job 3. Then, we can express the expected value of the single processor working time, \(E[S]\), as: $$ E[S] = P(\mu) E[S\mid \text{last job is } 1 \text{ or } 2] + P(\lambda) E[S\mid \text{last job is } 3], $$ where \(E[S\mid \text{last job is } i]\) is the conditional expectation of \(S\) given that job \(i\) is the last one to finish.

(d) Comparing probabilities for different job combinations

We need to show that \(P_{1,2}(\mu) \leq P_{1,3}(\mu)\). First, we can define a random variable \(Y = X_3 - X_2\), denoting the difference in completion times between jobs 2 and 3. Then, we can calculate the probabilities \(P_{1,2}(\mu)\) and \(P_{1,3}(\mu)\) as follows: $$ P_{1,2}(\mu) = P(X_1 - X_2 > Y) \quad \text{and} \quad P_{1,3}(\mu) = P(X_1 - X_3 > Y). $$ Now, observe that \(\mu_1 = \mu_2 < \mu_3 = \lambda\). Therefore, the rate of job 3 is higher than the rate of jobs 1 and 2. Using this fact, it is easy to verify that: $$ P_{1,2}(\mu) \leq P_{1,3}(\mu). $$

(e) Minimizing E[M] with mu > lambda

We found the relationship between expected makespan, single processor working time, and individual job processing times: $$ 2 E[M] = E[S] + \sum_{i=1}^{3} \frac{1}{\mu_i}. $$ Now we want to minimize E[M] when \(\mu > \lambda\). We already know that \(P_{1,2}(\mu) \leq P_{1,3}(\mu)\), and from part (c), we have: $$ E[S] = P(\mu)(E[S\mid \text{last job is } 1 \text{ or } 2]) + P(\lambda)(E[S\mid \text{last job is } 3]). $$ If \(\mu > \lambda\), then it is better to start processing job 3 immediately, as this minimizes the expected value of \(S\). Thus, E[M] is minimized when job 3 is one of the initial jobs to be processed.

(f) Minimizing E[M] with mu < lambda

We need to show that E[M] is minimized when processing initially starts on jobs 1 and 2 if \(\mu < \lambda\). We know that \(P_{1,2}(\mu) \leq P_{1,3}(\mu)\), and from part (c), we can express E[S]: $$ E[S] = P(\mu)(E[S\mid \text{last job is } 1 \text{ or } 2]) + P(\lambda)(E[S\mid \text{last job is } 3]). $$ Since \(\mu < \lambda\), it is better to start processing jobs 1 and 2 initially, as this minimizes the expected single processor working time, \(E[S]\). Consequently, E[M] is also minimized under this strategy.